DeepRL · 5月22日

DQN系列(1):Double Q-learning

首发深度强化学习实验室
作者:DeepRL

深度强化学习实验室报道

作者:DeepRL

image.png论文地址: https://papers.nips.cc/paper/...

本论文由DeepMind发表于2015年NIPS的一篇论文,作者Hasselt。

前言: Q-Learning算法由于受到大规模的动作值过估计(overestimation)而出现不稳定和效果不佳等现象的存在,而导致overestimation的主要原因来自于最大化值函数(max)逼近,该过程目标是为了最大的累计期望奖励,而在这个过程中产生了正向偏差。而本文章作者巧妙的是使用了两个估计器(double estimator)去计算Q-learning的值函数,作者将这种方法定义了一个名字叫“Double Q-learning”(本质上一个off-policy算法),并对其收敛过程进行了证明(缺点:当然double Q-learning算法有时会低估动作值,但不会像Q学习那样遭受过高估计)

1. 问题及原因

"过估计" (overestimate)

过估计是指_对一系列数先求最大值再求平均,通常比先求平均再求最大值要大(或相等_,数学表达为:image.png

一般来说Q-learning方法导致overestimation的原因归结于其更新过程,其表达为:
image.png
其中的image.png  表示为最大化action-value, 而更新最优化过程如下:
image.png
对于任意的image.png 来说,最优值函数 image.png 的更新依赖于image.png , 从公式中可以看出,我们把N个Q值先通过取max操作之后,然后求平均(期望),会比我们先算出N个Q值取了期望之后再max要大。这就是overestimate的原因。

注: 一般用于加速Q-learning算法的方法有:Delayed Q-learning, Phased Q-learning, Fitted Q-iteration等

2. Estimator原理与思想

通常情况下对于一个集合中的变量image.png 来说,奖励的最大化累计期望表示为:image.png

那么在实际的过程中,对于每个image.png ,我们定义 image.png为采样,其中的 image.png 表示为对于所有image.png采样的一个子集,假设 image.png 满足独立同分布情况, 那么期望值的“无偏估计”可以通过计算每个变量的样本平均值来获得,其计算方法如下:
image.png

image.png

这个过程是一个无偏估计,因为每一个采样image.png 是一个对 image.png 的无偏估计,因此,近似中的误差仅由估计中的 “方差“ 组成,当我们获得更多样本时会减小。

为了后面方便理解,这里我们定义两个函数:“概率密度函数”(Probability Density Function, PDF)和“累积分布函数”(Cumulative Distribution Function, CDF),概率密度函数image.png表示image.pngimage.png ,则累积分布函数表示为:image.png ,同样的道理,对于PDF和CDF来说估计器分别表示为image.pngimage.png

补充1. 概率密度函数, 其实就是给定一个值, 判断这个值在该正态分布中所在的位置后, 获得其他数据高于该值或低于该值的比例,其中的曲线就是概率密度函数(PDF),通常情况下pdf的曲线下面积(AUC)总和为1,且曲线末端不会接触到x轴(换句话说, 我们不可能100%的确定某件事)。image.png

2. 累积分布函数累积分布函数 (CDF) 计算给定 x 值的累积概率。可使用 CDF 确定取自总体的随机观测值将小于或等于特定值的概率。还可以使用此信息来确定观测值将大于特定值或介于两个值之间的概率。image.png例如,罐装苏打水的填充重量服从正态分布,且均值为 12 盎司,标准差为 0.25 盎司。概率密度函数 (PDF) 描述了填充重量的可能值的可能性。CDF 提供每个 x 值的累积概率。_此处参考__PDF-CDF指导_

(1)单估计器方法(Single Estimator)

所谓的单估计就是使用一组估计量的最大值作为近似值,

即近似image.png的最好的方式就是最大化估计器,表示为:
image.png
image.png表示为估计器image.png,而此处对于最大的估计器来说,它是依赖于image.png  的,若要求取PDF,首先需要考虑CDF,但它的概率分布中最大的估计器小于等于x,这等同于所有的估计均小于等于x,数学表示为:
image.png
那么image.png是对image.pngimage.png的无偏估计,详细表示为:
image.png

(2)双估计器方法(Double Estimator)

对每个变量使用两个估计器,并将估计器的选择与其值解耦。

问题:单一估计器方法导致过高估计可能会对使用此方法的算法(例如Q学习)产生很大的负面影响。为了解决这个问题,double estimator方法用来解决过高估计。

那么对于原来的image.png 来说,此处我们需要定义两个估计器:image.pngimage.png,他们分别表示为:image.png,,然后两个估计器都使用采样的样本子集来更新,其规则表示为:
image.png

那么像单估计器image.png一样,如果我们假设样本以适当的方式(例如随机地)分布在两组估计器上,则image.pngimage.png也都是无偏的。设image.png  为image.png 中最大估计值集合,由于image.png是一个独立的无偏估计值,那么 image.png对于任何j都成立,包括image.png 

此处有疑问,为什么包括??image.png

image.png

具体证明过程部分如下:image.png

3. Double Q-learning算法

我们可以解释为 Q-learning学习其实使用单估计器(single estimate)去估计下一个状态:那么image.pngimage.png的一个估计,一般的,将期望理解为对同一实验的所有可能运行的平均,而不是(通常在强化学习环境中使用)对下一个状态的期望,根据原理部分,Double Q-learning将使用两个函数image.png(对应两个估计器),并且每个函数Q都会使用另一个Q函数的值更新下一个状态。两个函数Q都必须从不同的经验集中学习,这一点很重要,但是要选择要执行的动作可以同时使用两个值函数。 因此,该算法的数据效率不低于Q学习。 在实验中作者为每个动作计算了两个Q值的平均值,然后对所得的平均Q值进行了贪婪探索。算法伪代码如下image.png

为了区分Double Q-learning算法和Q-learning的区别,本文同样Q-learning算法伪代码贴出来了。image.png

对比:此处对于Q-learning算法和double Q-learning 算法来说,double使用了B网络来更新A网络,同样的道理对于B网络则使用A网络的值来更新。

4. 实验过程于结果

image.png
在这里插入图片描述

5. 附录:收敛性证明过程

对于Double Q-learning收敛性的证明过程如下:

image.png

image.png

原文博客地址:

https://blog.csdn.net/gsww404...


推荐阅读

专注深度强化学习前沿技术干货,论文,框架,学习路线等,欢迎关注微信公众号。
深度强化学习实验室.png
更多深度强化学习精选知识请关注深度强化学习实验室专栏,投稿请联系微信 1946738842.

3 阅读 180
推荐阅读
0 条评论
关注数
32
文章数
18
专注深度强化学习前沿技术,欢迎关注
目录
极术微信服务号
关注极术微信号
实时接收点赞提醒和评论通知
Arm中国学堂公众号
关注Arm中国学堂
实时获取免费 Arm 教学资源信息
Arm中国招聘公众号
关注Arm中国招聘
实时获取 Arm 中国职位信息