Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

双Q学习

Q-learning 相关算法通常会过高的估计在特定条件下的动作值。这样做法存在一定的风险,由于不能确定这样的过高估计是否具备通用性,对性能会不会有损耗,以及是否能从主体上进行组织。Hado van Hasselt,Arthur Guez和David Silver在论文《Deep Reinforcement Learning with Double Q-learning》主要解决了这个问题。特别的,该文指出最近的 DQN 算法,的确存在特定动作在运行 Atari 2600 (Atari 2600 是一个家庭视频游戏)时会遭受严重的高估。该算法提出了double Q-learning algorithm可以很好的降低观测到的过高估计动作的问题,而且在一些游戏上取得了更好的效果。

来源:cnblog
简介

摘要:

Q-learning 相关算法通常会过高的估计在特定条件下的动作值。这样做法存在一定的风险,由于不能确定这样的过高估计是否具备通用性,对性能会不会有损耗,以及是否能从主体上进行组织。Hado van Hasselt,Arthur Guez和David Silver在论文《Deep Reinforcement Learning with Double Q-learning》主要解决了这个问题。特别的,该文指出最近的 DQN 算法,的确存在特定动作在运行 Atari 2600 (Atari 2600 是一个家庭视频游戏)时会遭受严重的高估。该算法提出了double Q-learning algorithm可以很好的降低观测到的过高估计动作的问题,而且在一些游戏上取得了更好的效果。

强化学习的目标(Sutton和Barto 1998)是通过优化累积的未来奖励信号来学习顺序决策问题。 Q学习(Watkins 1989)是最受欢迎的强化学习算法之一,但众所周知,它有时会学习不切合实际的高动作值,因为它包含了一个超过估计动作值的最大化步骤,这往往更倾向于有个高估值的问题。

为了解决序列决策问题,算法需要学习对每一个动作的最优值的估计。最优值的估计被定义为:当采取该行动,并且也采用最优的策略时,期望得到的将来奖励的总和。在给定一个策略π之后,在状态s下的一个动作 a 的价值为,也称为动作估值函数(action-value function):

Q_\pi {(s,a)} ==E[R_1+ \gamma R_2+...|S_0=s,A_0=a,\pi]

Image.jpg

其中 \gamma \in [0,1],它是一个衡量当前影响的系数。最优的值就是Q_\ast (s,a)=max_\pi Q_\pi(s,a)。一个优化的策略就是从每一个状态下选择最高值动作,也就是奖励值最高的值。

预测最优动作值可以利用Q-learning算法。大部分的问题(Watkins, 1989) (Sutton, 1988)无法在所有状态下(计算量太大)都计算出其动作值。而学习一个参数化的动作函数 Q(s, a; \theta_t),在状态S_t下,采取了动作 A_t之后,标准的Q-learning进行更新,然后观测到奖励 Rt+1以及得到转换后的状态St+1:

\theta_{t+1} = \theta_t +\alpha (Y_t^Q - Q(S_t,A_t;\theta_t)\triangledown _\theta_t Q(S_t,A_t;\theta_t))

Image.jpg \alpha 是步长。Q-Learning需要使用某一个policy来生成动作,也就是说这个采取的policy不是优化的那个policy,所以Q-Learning算法叫做Off-policy的算法。另一方面,因为Q-Learning完全不考虑model模型也就是环境的具体情况,只考虑看到的环境及reward,因此是model-free的方法。

其中,目标函数 Y^Q_t 的定义为:

Y^Q_t \equiv R_{t+1} + \gamma max_\alpha Q(S_{t+1},a; \theta_t)

Image.jpg

γ为折扣因子(discount factor)。折扣因子γ越大,maxQ所起到的作用就越大。在这里,可以理解为眼前利益(R),和记忆中的利益。

maxQ指的便是记忆中的利益。它是指记忆里下一个状态的动作中效用值的最大值。如果在下一个状态的某个动作上吃过甜头(选择了某个动作之后获得了50的奖赏),那么它就更希望提早地得知这个消息,以便下回在状态可以通过选择正确的动作继续进入这个吃甜头的状态。γ越大,算法就会越重视以往经验,越小,算法只重视眼前利益(R)。

此更新方法和随机梯度下降具有相似的工作方式,会逐渐趋向目标值 Y^Q_t 来更新当前值 Q(S_t, A_t; \theta_t)。

Deep Q-Networks:

基于价值的深度强化学习不仅仅是把 Q Learning 中的价值函数用深度神经网络近似,还做了其他改进。

这个算法就是著名的 DQN 算法,由 DeepMind 在 2013 年在 NIPS 提出。DQN 算法的主要做法是 Experience Replay,其将系统探索环境得到的数据储存起来,然后随机采样样本更新深度神经网络的参数。

DQN是多层的神经网络,给定一个状态 s,输出一个动作值的向量 Q(s,∗;θ),其中,θ是网络的参数。对于一个n维的状态空间,动作空间是m个动作,神经网络是一个函数将状态从n维空间映射到m维的动作空间。Mnih et al. (2015)所提出的DQN算法中,两个重要的特征分别是目标网络(target network)和经验回放技术(experience replay)的使用。

经验回放技术(experience replay)就是将系统探索环境获得的样本保存起来,然后从中采样出样本以更新模型参数。

目标网络: 在TD误差计算中,目标函数经常用DNN(Deep Neural Network (DNN))改变。 不稳定的目标功能使训练变得困难。 因此,目标网络修复了目标功能的参数,并且每千步更换一次最新的网络。目标网络(参数为\theta_t^-)的概念是用旧的深度神经网络 \theta_t^- 去得到目标值。Target网络的参数是每τ步从在线网络拷贝下来的。因此\theta_t^-=\theta_t,并且使得它们在其他的步中保持不变。因此,目标网络的表达式为:

Image.jpg

Y^{DQN}_t = R{t+1} + \gamma max_\alpha Q(S_{t+1},a; \theta_t^-)

Image.jpg

对于experience replay(经验回放技术)(Lin, 1992),观测到的转变都被在一定时间内存储,并且随机的从中进行采样,用来更新网络。目标网络和经验回放都明显的改善了最终的性能。

Double Q-learning:

在公式(2)(3)中标准的 Q-learning 以及 DQN上的最大化操作,是用相同的值来选择和评价一个行动。这使得其更偏向于选择过分评估值( overestimated values),导致次优的估计值。为了防止此现象,Double Q-learning从评价中将选择独立出来,这就是 Double Q-learning 背后的想法。

在最开始的 Double Q-learning (van Hasselt 2010)算法中,通过随机给每一个经验赋值来更新两个价值函数(value functions )中的一个,以便学习这两个价值函数(value function),如此,就得到两个权重的集合,θ以及θ′。对于每一次更新,其中一个权重的集合是用来决定贪婪策略,另一个权重集合用来决定其它的值的。做一个明确的对比,可以首先对 Q-learning中的选择和演化操作进行重新编排,重写公式2,得到:

Y^{Q}t = R{t+1} + \gamma Q(S_{t+1}, argmax_\alpha Q(S_{t+1},a;\theta_t);\theta_t)

Image.jpg

那么, Double Q-learning error可以写为: 

Y^{double_Q}t = R{t+1} + \gamma Q(S_{t+1}, argmax_\alpha Q(S_{t+1},a;\theta_t);{\theta}'_t)

Image.jpg 注意到在 argmax 中行动的选择仍旧取决当前的权重θ_t。这意味着,像 Q-learning一样,该算法仍然可以根据当前值,利用贪婪策略进行价值的估计。然而,利用第二个权重 θ^′_t来更加公平的评价该策略。第二个权重的集合,可以通过交换两个权重θ和θ′ 的角色进行更新。

Double DQN

Double Q学习的想法是通过将目标中的最大操作分解为动作选择和动作评估来减少过高估计。 虽然没有完全解耦合,但DQN架构中的目标网络为第二个值函数提供了自然的候选值,而无需引入额外的网络。

因此,这里建议根据在线网络评估贪婪策略,但使用目标网络估算其价值。 根据Double Q-learning和DQN,我们将得到的算法称为Double DQN。 它的更新与DQN相同,但用目标Y_t^{ DQN}替换:

image.png

Y_t^{DoubleDQN}= R_{t+1}+\gamma Q(S_{t+1},argmax_\alpha Q(S_{t+1},\alpha; \theta_t),\theta_t^-)

Double DQN中计算target使用了两个不同的θ,分别来自当前的q-network 以及目标q-network。当前q-network负责选择动作,而带有delayed θ的目标q-network来计算目标Q值。

与双Q学习相比,第二网络\theta_t^'的权重被替换为目标网络的权重\theta_t^-,用于评估当前贪婪策greedy policy, ϵ。 对目标网络的更新与DQN保持不变,并且仍然是在线网络的定期副本。Double DQN可能对DQN和Double Q-learning最小的改变。 目标是获得双Q学习的大部分好处,同时保持DQN算法的其余部分完整无缺,以进行公平比较,并且计算开销最小化。

【出处:https://www.cnblogs.com/wangxiaocvpr/p/5620365.html

2. 发展历史

描述

到这里为止,在Q学习的基础上,DQN的大致演进路线如下。

1989年,Watkins在自己的博士论文(Learning from delayed rewards)中最早提出Q学习算法。1992年,Watkins和Dayan在机器学习的一个技术笔记(Technical note)给出了Q学习的收敛性证明,证明了当所有的状态都能重复访问时,Q函数最终会收敛到最优Q值. 1989年由Watkins提出的Q学习是一种model-free(不用学习环境模型)的基于off-policy(学习过程中执行的策略与值估计使用的策略不一样)的temporal difference(TD)方法,也是RL中流传最为广泛的一种学习方法。2010年,Hasselt, H. V.提出Double Q-learning。

强化学习(Sutton and Barto 1998) 的目标是对序列决策问题能够学习到一个好的策略,通过优化一个累计未来奖励信号。而Q-learning (Watkins 1989) 是最著名的 reinforcement learning 学习算法之一,但是由于其在预测动作值的时候包含一个最大化的步骤,所以导致会出现过高的预测值,使得学习到不实际的高动作值。

2013年,DeepMind在NIPS发表了Playing atari with deep reinforcement learning论文,论文中主体利用深度学习网络(CNNs)直接从高维度的感应器输入(sensory inputs)提取有效特征,然后利用Q-Learning学习主体的最优策略。这种结合深度学习的Q学习方法被称为深度Q学习(DQL)。

2015年初,DeepMind在Nature发表了DQN的改进版论文,论文使用了经验回放(Experience Replay)技术以及增加一个目标网络(Target Network),改善了原始版DQN在实际训练中不稳定的问题。为进一步改善DQN在训练中不稳定的问题,Hado Van Hasselt等提出周期性地冻结目标网络的Double DQN(Deep Reinforcement Learning with Double Q-Learning),Tom Schaul等提出prioritized experience replay的方法提高抽样效率,Wang Ziyu等提出Dueling DQN的网络结构,通过将Q函数(Q(s, a))分解成状态函数(V(s))和优势函数(A(a))可以学习到更健壮的状态函数值。

研究者发现,Q学习中的overestimation问题(在确定状态下Q值估计偏高)可能导致非最优解和学习过程稳定性下降。最初Thrun & Schwartz开始探讨该问题,证明了在使用函数逼近器时overestimation可能导致非最优解。之后van Hasselt发现即使用表格表示法的情况下,环境中的噪声也能导致overestimation,并且提出了解决方案Double Q-learning。而DQN是基于Q-learning,所以本质上也有这个问题。因此将Double Q-learning结合进DQN可以改善。其基本思想是将选择和评估动作分离,让它们使用不同的Q函数(网络)。其中一个用于产生贪婪策略(greedy policy),另一个用于产生Q函数估计值。实现时会有两个Q函数网络:原DQN中的Q函数网络称为在线网络(online network),后者称为目标网络(target network)。由于Nature版DQN已经引入了单独的Q目标网络,所以Double DQN对DQN架构基本不需什么改动,只需把目标网络的参数和在线网络的参数独立训练即可。注意和本文方法相比,Nature 2015上的方法相当于是参数的延迟更新,在同一步更新的动作选取和函数估计中还是用的同一个参数。

【出处:https://blog.csdn.net/jinzhuojun/article/details/52752561

主要事件

年份事件相关论文
1989年Watkins在自己的博士论文中首先提出Q学习这一概念Watkins, C. J. C. H. (1989). Learning from delayed rewards (Doctoral dissertation, King's College, Cambridge).
1992年Watkins和Dayan给出了Q学习算法的详细证明,只要主体所有的动作都能在所有的状态下重复抽样,Q学习最终能百分之百收敛到最优的策略值。Watkins, C. J., & Dayan, P. (1992). Q-learning. Machine learning, 8(3-4), 279-292.
1998Sutton, R. S., Barto, A. G., & Bach, F.du提出强化学习Sutton, R. S., Barto, A. G., & Bach, F. (1998). Reinforcement learning: An introduction. MIT press.
2010Hasselt, H. V.提出Double Q-learningHasselt, H. V. (2010). Double Q-learning. In Advances in Neural Information Processing Systems (pp. 2613-2621).
2013年DeepMind发表了第一版本的DQNMnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., & Riedmiller, M. (2013). Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602.
2015年DeepMind在Nature上发表了改进版的DQN,运用了experience replay以及target network等技术来改善DQN的训练收敛性问题Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., ... & Petersen, S. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529-533.
2016Van Hasselt, H., Guez, 提出Deep Reinforcement Learning with Double Q-learningVan Hasselt, H., Guez, A., & Silver, D. (2016, February). Deep Reinforcement Learning with Double Q-Learning. In AAAI(Vol. 2, p. 5).Van Hasselt, H., Guez, A., & Silver, D. (2016, February). Deep Reinforcement Learning with Double Q-Learning. In AAAI(Vol. 2, p. 5).

3. 发展分析

瓶颈

拿特定数据集上的准确性进行比较,但一定程度上忽略了通用性也是机器学习走向大众最大瓶颈之一的事实。

【来源:web, URL:http://lib.csdn.net/article/aimachinelearning/50797

未来发展方向

今天的的人工智能和机器学习领域,工程和学术同样重要。一方面可能因为DL的特殊性,毕竟它基于的神经网络从一开始就是偏工程的;另一方面今天的工业与学术结合更加紧密,产业化速度大大加快。比如DRL的idea很好,但前提是要有工程能力证明它的有效性。即使有学者早期已经开发出了这个idea,但缺乏实践的验证它仍不具备巨大的科学意义,因此也无法发表在Nature这样的高级别学术刊物上。因为今天的DRL是工程和学术的充分结合。另外,这还提醒我们要重视学科或者说是方向的交叉。很多时候,一篇论文的学术价值取决于它能给后人留多少可以继续深究的东西。除了那些能自成一派的高级人才,大多数时候能连接两个或多个方向并证明其价值所带来的影响就非常深远了。

【来源:web, URL:http://lib.csdn.net/article/aimachinelearning/50797

Contributor: Ruiying Cai

简介