当深度强化学习遇见图神经网络

2019 年 10 月 21 日 专知

导读

本文提出将图神经网络(GNN)与深度强化学习(DRL)相结合。新的DRL+GNN体系结构能够在任意网络拓扑图上学习、操作和生成。作者认为缺乏泛化是阻碍在生产网络中部署现有的基于DRL的解决方案的主要障碍。因此,所提出的体系结构是开发新一代基于DRL的网络产品的第一步。


作者 | Paul Almasan等

编译 | Xiaowen


论文PDF下载

请关注专知公众号(点击上方蓝色专知关注
  • 后台回复“DRL-GNN” 就可以获取《 Deep Reinforcement Learning meets Graph Neural Networks》的完整版PDF下载链接~


深度强化学习(Deep Reinforcement Learning, DRL)的最新进展在决策问题上显示出了重要的改进。网络社区已经开始研究DRL如何为相关的优化问题(如路由routing)提供新的解决方案。然而,大多数最先进的基于DRL的网络技术无法生成(generalize),这意味着它们只能在训练期间看到的网络拓扑图上运行,而不能在新的拓扑图上运行。这一重要限制背后的原因是,现有的DRL网络解决方案使用标准的神经网络(例如全连接),无法学习图形结构的信息。本文提出将图神经网络(GNN)与DRL相结合。GNN最近被提出用于图形建模,我们的新的DRL+GNN体系结构能够在任意网络拓扑图上学习、操作和生成。为了展示它的泛化能力,我们在光传输网络(OTN)场景中对其进行了评估,在该场景中,智能体(agent)需要高效地分配通量(traffic)需求。我们的结果表明,我们的DRL+GNN智能体能够在训练过程中看不到的拓扑结构中取得优异的性能。


本文提出的解决方案结合了两种机器学习机制。首先,我们使用图神经网络(GNN)对计算机网络进行建模。其次,我们使用深度强化学习(DRL)来构建学习如何按照特定的优化目标有效地操作网络的智能体。 

图神经网络(Graph Neural Networks,GNN)是一种新型的神经网络,用于对图结构信息进行操作。它们的基本形式是将一些初始状态与图中的不同元素相关联,然后结合这些元素在图中的相互关系。迭代算法更新状态元素并使用最终状态产生输出。要解决的问题的特殊性将决定使用哪种GNN变体,考虑图的哪些元素(边或节点)等等。


图1. 信息传递的单步概览。

DRL算法的目标是学习一种策略,使优化问题的累积报酬最大化。DRL智能体从tabula rasa开始。这意味着他们以前对他们经营的环境没有专家知识。他们只有一组可能的行动,并在探索行动和观察空间的迭代过程之后学习最优策略。该学习过程由一组动作A和一组状态S组成。给定一个状态s∈S,Agent将执行一个a∈A的动作,该动作产生一个新的状态s∈S的转换,并提供一个奖励r,这个优化问题可以被建模为一个马尔可夫决策过程(MDP)。然而,对于MDP的解决方案,需要评估状态-动作对的所有可能组合。

图2. OTN路由场景中DRL智能体的示意图表示。

本文提出了DRL+GNN智能体,我们的智能体实现了DQN算法,其中Q值函数是用GNN建模的。算法1详细说明了伪代码,包括训练过程。



图3中展示了了在训练期间基于GNN的模型的评估分数。还展示了ϵ在训练过程中的演变过程。


图3. 训练期间evaluation平均eps=50次测试分数。



图4展示了基于GNN的DRL智能体在GBN上相对于SAP启发式和RAND策略的性能,后者表示在所有最短可用路径上的随机路径选择。可以将此策略视为负载平衡策略,因为路径是一致选择的。y轴代表超过50个评估集(x轴)的得分.横线表示每个策略在所有事件中获得的平均分数。这个图显示了我们的DRL智能体保持良好性能的能力,即使它在一个在训练中没有看到不同拓扑的路由场景中运行时也是如此。

图4. 基于GNN的DRL智能体性能与SAP和RAND策略的比较。


本文提出了一种基于GNNs的DRL体系结构,能够推广到不可见的网络拓扑。 使用GNNs对网络环境建模,允许DRL智能体在不同网络中操作,而不是只在用于训练的网络中。 我们认为,缺乏泛化是阻碍在生产网络中部署现有的基于DRL的解决方案的主要障碍。 因此,所提出的体系结构是开发新一代基于DRL的网络产品的第一步。


-END-
专 · 知


专知,专业可信的人工智能知识分发,让认知协作更快更好!欢迎登录www.zhuanzhi.ai,注册登录专知,获取更多AI知识资料!
欢迎微信扫一扫加入专知人工智能知识星球群,获取最新AI专业干货知识教程视频资料和与专家交流咨询
请加专知小助手微信(扫一扫如下二维码添加),获取专知VIP会员码,加入专知人工智能主题群,咨询技术商务合作~
点击“阅读原文”,了解注册成为专知VIP会员
登录查看更多
224

相关内容

深度强化学习 (DRL) 是一种使用深度学习技术扩展传统强化学习方法的一种机器学习方法。 传统强化学习方法的主要任务是使得主体根据从环境中获得的奖赏能够学习到最大化奖赏的行为。然而,传统无模型强化学习方法需要使用函数逼近技术使得主体能够学习出值函数或者策略。在这种情况下,深度学习强大的函数逼近能力自然成为了替代人工指定特征的最好手段并为性能更好的端到端学习的实现提供了可能。
【ICML2020】持续图神经网络,Continuous Graph Neural Networks
专知会员服务
145+阅读 · 2020年6月28日
多智能体深度强化学习的若干关键科学问题
专知会员服务
171+阅读 · 2020年5月24日
注意力图神经网络的多标签文本分类
专知会员服务
111+阅读 · 2020年3月28日
【图神经网络(GNN)结构化数据分析】
专知会员服务
112+阅读 · 2020年3月22日
图神经网络表达能力的研究综述,41页pdf
专知会员服务
167+阅读 · 2020年3月10日
深度强化学习策略梯度教程,53页ppt
专知会员服务
175+阅读 · 2020年2月1日
专知会员服务
198+阅读 · 2019年8月30日
图神经网络(Graph Neural Networks,GNN)综述
极市平台
103+阅读 · 2019年11月27日
GraphSAGE: GCN落地必读论文
AI100
29+阅读 · 2019年8月15日
图神经网络火了?谈下它的普适性与局限性
机器之心
21+阅读 · 2019年7月29日
赛尔笔记 | 一文读懂图神经网络
哈工大SCIR
81+阅读 · 2019年7月12日
掌握图神经网络GNN基本,看这篇文章就够了
新智元
161+阅读 · 2019年2月14日
TensorFlow 2.0深度强化学习指南
云栖社区
18+阅读 · 2019年2月1日
清华大学图神经网络综述:模型与应用
机器之心
72+阅读 · 2018年12月26日
图神经网络综述:模型与应用
PaperWeekly
193+阅读 · 2018年12月26日
深度强化学习的弱点和局限(上)
论智
8+阅读 · 2018年2月26日
Tutorial on NLP-Inspired Network Embedding
Arxiv
7+阅读 · 2019年10月16日
Arxiv
15+阅读 · 2019年6月25日
A Comprehensive Survey on Graph Neural Networks
Arxiv
21+阅读 · 2019年1月3日
Deep Graph Infomax
Arxiv
16+阅读 · 2018年12月21日
Deep Reinforcement Learning: An Overview
Arxiv
17+阅读 · 2018年11月26日
Arxiv
5+阅读 · 2018年6月5日
VIP会员
相关VIP内容
【ICML2020】持续图神经网络,Continuous Graph Neural Networks
专知会员服务
145+阅读 · 2020年6月28日
多智能体深度强化学习的若干关键科学问题
专知会员服务
171+阅读 · 2020年5月24日
注意力图神经网络的多标签文本分类
专知会员服务
111+阅读 · 2020年3月28日
【图神经网络(GNN)结构化数据分析】
专知会员服务
112+阅读 · 2020年3月22日
图神经网络表达能力的研究综述,41页pdf
专知会员服务
167+阅读 · 2020年3月10日
深度强化学习策略梯度教程,53页ppt
专知会员服务
175+阅读 · 2020年2月1日
专知会员服务
198+阅读 · 2019年8月30日
相关资讯
图神经网络(Graph Neural Networks,GNN)综述
极市平台
103+阅读 · 2019年11月27日
GraphSAGE: GCN落地必读论文
AI100
29+阅读 · 2019年8月15日
图神经网络火了?谈下它的普适性与局限性
机器之心
21+阅读 · 2019年7月29日
赛尔笔记 | 一文读懂图神经网络
哈工大SCIR
81+阅读 · 2019年7月12日
掌握图神经网络GNN基本,看这篇文章就够了
新智元
161+阅读 · 2019年2月14日
TensorFlow 2.0深度强化学习指南
云栖社区
18+阅读 · 2019年2月1日
清华大学图神经网络综述:模型与应用
机器之心
72+阅读 · 2018年12月26日
图神经网络综述:模型与应用
PaperWeekly
193+阅读 · 2018年12月26日
深度强化学习的弱点和局限(上)
论智
8+阅读 · 2018年2月26日
相关论文
Tutorial on NLP-Inspired Network Embedding
Arxiv
7+阅读 · 2019年10月16日
Arxiv
15+阅读 · 2019年6月25日
A Comprehensive Survey on Graph Neural Networks
Arxiv
21+阅读 · 2019年1月3日
Deep Graph Infomax
Arxiv
16+阅读 · 2018年12月21日
Deep Reinforcement Learning: An Overview
Arxiv
17+阅读 · 2018年11月26日
Arxiv
5+阅读 · 2018年6月5日
Top
微信扫码咨询专知VIP会员