郝建业:从囚徒困境到自动驾驶,蛰伏数十载的多智能体强化学习,期待破茧成蝶
作者 | 青暮
编辑 | 王晔
2019年郝建业的团队获得了 第一届DAI最佳论文奖 ,距离他那篇研究 多智能体系统中的“囚徒困境”论文 的发表时间,已经整整过去了 11年 。
郝建业也没有想到,当初那篇只是基于简单博弈场景的研究成果,几乎被遗忘。如今通过结合深度强化学习,用于处理更复杂的场景,竟一下子成为了聚光灯下的宠儿,“仔细看DAI这篇文章里面的一些设计,其实都能在我以前的工作里找到原型。”
相对于以前的工作,这篇DAI 2019论文提出的模型,在参数空间上更加复杂, “尽管仍然是demo,但也是从理论走向实践的关键一步。”
在近期,AI科技评论与天津大学副教授、华为诺亚方舟实验室科学家郝建业进行了交流,谈了谈他从读博到科研工作期间的学术历程,试图理解他在十几年内,从简单的囚徒困境,跨越到复杂的 囚徒困境 ,乃至自动驾驶等实际场景的研究和落地时,背后所付出的汗水,支撑他的信念,以及多智能体强化学习领域的时代剪影。
1
2009年7月,郝建业入学香港中文大学攻读博士学位,拜师 梁浩锋 ,开启了多智能体系统和强化学习的研究之路。在当时,多智能体系统以及强化学习这两个方向都还属于冷门领域。
梁浩锋教授 是香港中文大学计算机科学与工程学系教授和社会学系教授,研究领域包括多智能体系统、博弈论分析、本体(知识图谱)和大数据分析等。
在郝建业的印象中,当时这两个方向的研究对象也还很简单,一般这些博弈问题都能以表格的形式表示。 在深度强化学习概念还没有形成的那个时期,学者们研究的场景都是相当局限的,也就是 基于表格的强化学习 。
著名的囚徒困境就是一个典型的博弈场景,可以用下表来表示,在逼供场景下,囚徒有两个选择。
在囚徒困境问题中,囚徒不仅困于监狱,亦困于仅有两个选择 。但这些研究更多是在提出新的概念、范式、机制,偏向于理论,对于博弈论而言仍然具有很大的贡献。
而彼时更受欢迎的是不包括深度学习的模式识别,数据挖掘等方向,但在梁教授的引导下,郝建业还是慢慢喜欢上了这两个冷门方向。
2
然而在刚入学时,郝建业在数学和领域知识方面还是个“菜鸟”。
比如博弈论是多智能体系统中最关键的一套数学工具 ,为此,梁教授甚至专门为他开设了个人课堂。
看论文也是一门必修课,郝建业看遍了 AAMAS 近一两年的几乎所有相关论文,“泛读的至少几百篇,精读的也有几十篇。”按照当年打印论文的习惯,这些论文大概得有半米的高度。 AAMAS是多智能体领域最有影响力的会议,亦属于机器人领域顶会。
坚持啃论文差不多一年时间以后,郝建业才初步对多智能体方向建立了系统的认知,以及了解自己到底对哪个topic感兴趣。
“兴趣应该是做的过程中慢慢培养起来的。当你对某样东西一无所知的时候,也很难引发兴趣,而只是知道一个名词而已。比如现在很多学生说对人工智能感兴趣,但是你问对方‘什么是人工智能’,对方经常都答不上来,这种其实不是真正的兴趣,只是一时好奇。” 在与梁教授的接触中,郝建业才慢慢领悟到这个道理。
回溯至更早期时光,他恍然大悟。本科期间,他在 香港理工大学张大鹏教授 和 哈尔滨工业大学左旺孟教授 指导下做研究时,“尽管对AI没什么认知,但兴趣就是在那个时候萌芽的。”
梁教授奉行 “大方向把控,小方向自由” 的培养风格,因此会让学生花费大量时间自己去找方向,同时实验室的大方向都会聚焦在多智能体系统上。“这种培养方式,让我养成了非常独立的科研风格。”
如果导师在方方面面都管的太细,容易造成学生被动,视野狭窄。 “有了独立的思考方式,和广阔的研究视野和对方向脉络的把握,就知道怎么规划自己的未来方向,以及在做战略转型、跨界研究的时候,都能心中有数。”
这种自由又不同于放任的散养模式,在具体执行层面,梁教授可谓细致入微,在郝建业写的第一篇论文上,梁教授就加上了密密麻麻的红色批注。
3
在博士期间,郝建业选择了 公平性和社会利益最优 ,作为多智能体系统领域下的研究方向。
在那时候,团队以及相关领域的学者,都在研究怎么用强化学习等方法,在不同的博弈环境下快速学习到纳什均衡。 “纳什均衡是博弈论里最核心的概念,甚至上世纪90年代的很多相关工作都沿着这个方向来做。”
在博弈论中,纳什均衡是指在包含两个或以上参与者的非合作博弈中,假设每个参与者都知道其他参与者的均衡策略的情况下,没有参与者可以通过单方面改变自身策略使自身受益。
囚徒困境中两个囚徒都选择招供的策略,就是一个典型的纳什均衡解。两个囚徒无法与对方进行合作(或沟通),此时选择招供就会比不招供收益更大。
那么,这类研究存在什么问题呢?很明显,均衡解虽然稳定,但不一定是最好的解。在囚徒困境中,双方都不招供其实才是全局最优解,而全局最优解又存在不稳定的问题。此外,公平性问题也是存在的,即在一个均衡点上,每一方的利益不一定对等。
因此,郝建业就在探索, 怎么用强化学习的方法,让智能体有意愿、有动力、有理性地去学习到社会全局最优的、公平的解,以及研究是否存在新型的均衡解,即保留原始均衡稳定性的特点,同时有具备公平性,社会最优等属性,也就是从“策略层面”而言的均衡 (strategy equilibrium) 。
而当初那些基于表格的toy example,在深度强化学习的助力下,得以应对更加复杂的场景,智能体也得以产生更加多样化和灵活的决策。“反过来说, 如果我们细看现在的深度强化学习的代表工作,很多其实都是借鉴了上世纪90年代至2010年之前的工作,并扩展了深度学习方法。” 然而目前大部分深度强化学习下的工作还没有走到关注“策略均衡”的阶段,还停留在类比于“基于表格强化学习的多智能体系统研究“相对早期的阶段。
郝建业将“从简单到复杂”的理念贯彻至今,并 在2019年首届国际分布式AI大会上,以复杂场景的囚徒困境研究获得了DAI最佳论文奖 。这一次,囚徒不再限于两个选择,而是无限个,虽然这也只让其更自由了一点点。
经典囚徒困境对囚徒的决策选择做了很大限制,要么合作,要么背叛。但囚徒困境并不是凭空捏造的思维游戏,不只有《蝙蝠侠前传2》中的小丑会玩。
在现实世界,也存在因为无法完全信任或推测对方心理,导致选择相信就可能遭遇损失的情况。可以说,存在竞争和信任危机时都容易引发囚徒困境,比如战争,乃至任何形式的合作关系。毕竟,合作意味着妥协,意味着出让部分利益,这就让背叛者有机可乘。在论文中,郝建业等人将这种背叛行为称之为 “剥削” 。
因此,在这项工作中,郝建业等人应用深度强化学习,探索了在复杂场景下,能抵抗对手剥削,同时又能适当合作的智能体策略。这其中的关键点,就在于 推测对手心理 。
他们提出了一个合作度检测网络,它相当于一个心理模型。给定对方的一系列动作,来预测对方的合作程度。该网络结合了 LSTM 和 自编码器 ,可以保证对观察到的动作进行有效的特征提取,加快心理模型的训练速度,提高鲁棒性。
合作度检测网络
比如在 Apple-Pear 游戏中,有一个红苹果和一个绿梨。蓝色智能体喜欢苹果,而红色智能体喜欢梨。每个智能体有四个动作:上、下、左、右,每走一步都会产生 0.01 的成本。当智能体走到水果对应方格时,就能收集到水果。
当蓝色(红色)智能体单独收集一个苹果(梨)时,它会获得更高的奖励 1。当智能体收集到不喜欢的水果时,则只能获得更低的奖励 0.5。但是,当它们分享一个梨或一个苹果时,它们都会获得相应奖励的一半。
以合作度为度量,智能体可以产生更加多样化的决策。实验结果也不意外地显示, 这两个智能体合作程度越高,总体奖励越高。
郝建业将这种博弈场景称之为 序列囚徒困境(SPD) ,它更加接近于现实世界中的博弈过程,即 结合观察来随时调整策略。
训练方面,该方法包括两个阶段: 离线和在线阶段 。离线阶段生成不同合作度的策略并训练合作度检测网络。在线阶段则根据检测到的对手的合作程度,从连续的候选范围中自适应地选择具有适当合作程度的策略。
直观地说, 该算法是面向合作的,并且对对手的自私、剥削行为也有防御能力 。
论文地址:http://ala2018.it.nuigalway.ie/papers/ALA_2018_paper_18.pdf
科研更像是在撒播种子,学者们依靠期望和想象去支撑意志力,从而坚持不懈地耕耘。这一过程存在太大的不确定性,但每次或隔一个月、或隔十年回到原野时,都期盼能看到令人出乎意料的景观。
郝建业坦言, “尽管最初只是非常简单的模型,但时间的力量以及外部环境的助推,可以令其茁壮成长,并最终在现实中变成让我们惊叹的样子。”
他没有仅仅满足于增加问题复杂度,而是进一步将目光聚焦到了更贴近现实的层面—— 研究自动驾驶场景的多智能体系统 。
4
在华为诺亚方舟实验室,他和团队与上海交通大学、伦敦大学学院合作开发了一个自动驾驶模拟仿真平台—— SMARTS 。
SMARTS 针对的是仿真平台的两个限制性问题,一个是 环境单一 ,比如大部分仿真平台都只设置了晴天的天气;另一个则是 缺少与其它智能体的互动场景 ,比如下图中的“双重合并”。
可以说,多样的互动场景是 SMARTS 的一大特色。
SMARTS 的相关论文 “SMARTS: Scalable Multi-Agent Reinforcement Learning Training School for Autonomous Driving”发表在机器人顶会之一CoRL 2020上,并斩获最佳系统论文奖。
论文地址:https://arxiv.org/pdf/2010.09776.pdf
缺乏互动场景研究会导致一个问题,即自动驾驶汽车在遭遇复杂场景时,通常选择更加保守的策略,比如放慢速度,而不是主动寻找另一条出路。即便是采用了保守的方案,也不见得安全。
在 2018 年的加利福尼亚州,57% 的自动驾驶汽车事故是追尾事故,29% 是侧滑事故。所有这些都是其他汽车造成的,因此可以归因于自动驾驶汽车的保守性。
类比于自动驾驶汽车的L0-L5级别,郝建业等人在这项研究中提出了 “多智能体学习级别” ,或简称 “M级别” 。
其中,M0级别的智能体为完全遵守规则的保守派;M1级别的智能体可以在线学习,以增加应对未知情况的能力;M2级别的智能体要学会建模其他智能体,但还没有直接的信息交换;M3级别的智能体在训练期间会进行信息交换,在部署时则不需要;M4级别的智能体需要学会应对局域交互场景,比如十字路口会车,找到符合纳什均衡或其他均衡的策略;M5级别的智能体则需要在满足全局最优的前提下,去学习局域决策。
郝建业等人认为,迄今为止,自动驾驶研究主要集中在 M0,对 M1 和 M2 的尝试非常有限,而一个关键原因是 缺乏对道路上的异构智能体之间交互的合适模拟 。看来这个标准相比 “L级别” 要更加严苛。
在第二届DAI(DAI 2020)上,华为诺亚基于该平台举办了自动驾驶挑战赛, 郝建业回忆道,“比赛中,选手们没有局限于强化学习,提出了多种不同的解决方案,这是一个很好的现象。”
他进一步说道,“ SMARTS 有两方面的价值,一方面是它作为平台,可以让所有做相关研究的人针对自动驾驶的不同场景做相关算法的研究。另一方面,我们希望通过这个平台,生成多样化的真实社会模型,从而让自动驾驶算法在现实落地中安全、有效。”
17世纪,当伽利略观察金属球在光滑的斜面上滚过时,不会想到这背后的物理学支撑着如今在天空中飞驰的蜻蜓状庞然巨物。
多智能体强化学习从最初的表格学习,进化到今天的自动驾驶模拟,亦宛如完成了《2001太空漫游》中的史诗级蒙太奇一般。
相信时间之力量的信念,或许有一部分来自郝建业在 MIT 期间受到的潜移默化的影响。
5
2013年,郝建业博士毕业于香港中文大学,毕业后远走美国,在 MIT CSAIL 做博士后研究。
“CSAIL给我的整体感觉是,学术氛围非常浓厚。他们有最顶尖的人才,学生、老师之间交流起来没有隔阂,没有辈分顾虑,非常舒服,学术合作的效率也非常高。”
这种浓厚可以用“听不完的讲座,参加不完的学术竞赛和研讨会”来形容,也可以借鉴一句名言来体会。 MIT 第十三任校长、计算机科学与工程系教授 Jerome Weisner 曾经说过 “Getting an education from MIT is like taking a drinkfrom a fire hose.” 这句话是说,在麻省理工学院读书就像是从消防栓里喝水,“想想消防栓的水量,那是根本喝不完的。”
郝建业提到了一个有趣的细节。 MIT CSAIL 的学术大牛非常多,随随便便就能遇到,可能是你在食堂吃饭的时候,也可能是你在运动场上散步的时候,“我有一次在电梯里遇到了一位老学者 Silvio Micali ,其貌不扬,当时没注意,结果上课的时候才发现,那是我们的授课老师,而且拿了当年的图灵奖。”
Silvio Micali
“不仅是学校和老师, MIT 整体的学术氛围也造就了实验室博士生非常务实的研究风格,希望博士期间作出有影响力的工作,而不是盲目于发论文。如果没有做出自己满意的成果,很多学生会主动要求延毕,7年毕业对于他们而言是很正常的。”
如果一个 MIT 博士生毕业时的学术成果不行,就会被评价学术潜力一般,这对以后的发展会有很大影响。“因此,他们情愿延期一到两年,拿出有代表性的成果,再去找教职,或进入市场竞争。”
所谓的代表性成果,不是看论文数量,而是看工作的价值,“价值是要往长远去看的,不管是学术层面的奠基性作用,还是应用层面的普惠意义。”
在博士后期间,团队研究课题聚焦在基于 AI+形式化 的方法来实现 CPS 系统安全,团队大部分成员包括郝建业的导师、MIT计算机科学系教授 Daniel Jackson ,主要专注的领域是 形式化验证 。
6
形式化验证即是用数学方法验证系统是否存在bug ,比如在CPU设计中用计算机模拟验证是否存在潜在问题。因此, 形式化验证也可以叫软件模拟,重点在于预防错误发生 。
在这里,郝建业探索了另一条研究道路—— 学科交叉 。其实,在博士期间,他就在广泛地做多学科阅读,比如微观经济学、行为科学等等, “多智能体系统是一个交叉学科,不会局限于计算机科学。”
甚至在本科大三实习期间,郝建业第一次接触科研,也就是走进香港理工大学张大鹏教授的实验室时,做的也不是多智能体系统研究,而是生物信息学方面的工作,这也是他在哈工大王宽全教授指导下研究的方向。当时他做的课题是基于传统机器学习的舌头病变检测,除了数据准备,也要做特征提取。在郝建业的思维里, “AI不只有端到端,不只有深度学习” 的思想,从那时候就埋下了种子。
在 Daniel Jackson 的指导下,郝建业探索了将多智能体系统和形式化验证结合的方向,并卓有成效。
以智能交通为例,郝建业研究了如何在所有行人、车辆等智能体都遵循相同交通规则的前提下,保证行人、车辆之间都不会相撞,并找到满足条件的最少规则。这里, 相撞即是形式化验证中要寻找的bug 。
例如,为避免碰撞,两列自主列车在同一条隧道中行驶,可以执行“如果在隧道内观察到另一列列车,则不应允许移动动作”的规则。也就是说,这项工作尝试让AI自动设计最适合的交通规则,并能够自动化验证该套规则是否安全可靠。
在形式化规则约束下,对于交通系统中的每辆车而言,它们都只知道在当前局部场景下应该遵守的规则,和可选的决策,而不知道远处其它智能体的情况,但最终整个交通系统的效率能达到全局最优。研究结果也显示, AI找到的规则和手动设计的规则效果相当 。
而反观现实中常见的堵车问题,郝建业指出, “这本质上其实是缺乏规则共识。”每个人心中对于规则的认可程度都不一样,导致单一的形式化系统的预测在现实中根本匹配不上。人与自动驾驶汽车之间也存在类似关系,“有一个说法是,只有真人驾驶汽车的道路,与只有自动驾驶汽车的道路,在通畅度上也会更好。”
”多阅读交叉学科的文章,对以后的工作会有长期的启发性影响。” 郝建业在博士期间受到的提点,终于在这一刻有了真实的感悟。
在华为,郝建业也进一步将相关技术应用到了自动驾驶技术的研发上,“由于可以保证车辆之间不碰撞,形式化系统的结合对于自动驾驶的安全性非常重要。”
郝建业认为,“ 仿真技术 和 形式化验证 是两条差别比较大的路线,可以说是两个极端。其中基于深度强化学习的仿真技术笨一点,一般通过遍历所有可能场景来寻找可行的方案,而形式化验证则精一点,可以从理论上直接保证结果是可靠的,“但它们都是值得探索的方向,是互补的。”
在论文中,郝建业研究的也是相对简单的场景。 而如今,这项技术对于智能电网乃至智慧城市的开发都已具有非常重要的启发意义。
论文地址:https://groups.csail.mit.edu/sdg/pubs/2016/norms-fse16.pdf
多学科交叉的有效性或许也可以从历史中寻找渊源。 博弈论最早起源于经济学,但它的创始人,实际上是计算机之父冯·诺依曼 ,博弈论与计算机科学之间或许早就暗藏千丝万缕的联系,如今终于在AI时代被放大。
计算机科学在艾伦·图灵提出图灵机概念后,早就有了统治科学世界的野心。哪怕十分简陋,如今做科研谁能离开计算机呢?深度学习正好在人们困惑、嘲笑计算机只能处理代码,不能理解感官世界的丰富时,提供了一个连接桥梁。似乎在神经网络中,万物都能被统一为无数的电脉冲,不同学科之间的隔阂亦不再厚重和神秘。
7
游戏是一个庞大的虚拟世界,疫情的到来更是将无数被困现实的新玩家涌入,让这个虚拟世界急速扩张,而里面24小时活跃着的玩家、NPC都是多智能体系统天然的研究对象。
在与网易伏羲人工智能实验室、南洋理工大学等合作完成的论文“Wuji: Automatic Online Combat Game Testing Using Evolutionary Deep Reinforcement Learning”中,郝建业等人延续多学科交叉道路,研究了如何将演化学习与强化学习结合起来,提出了 动态游戏测试框架Wuji ,从而将游戏测试自动化,并提高效率。
论文地址:https://nos.netease.com/mg-file/mg/neteasegamecampus/art_works/20200812/202008122020238586.pdf
测试游戏潜在bug的一个难点,就是触发 ,“有些bug可能非常隐蔽,大部分玩家都不会触发,比如它可能在某个难度很高的关卡中,而一旦触发就会带来非常不好的体验。”
而现有深度强化学习主要聚焦于赢得胜利,获取高分,因此在开发探索能力上受限于目标,也就是奖励函数的设置。
例如,下图展示了一个简单的迷宫游戏,其中机器人需要寻找左上角的黄金。如果机器人到达图中标记的绿点、黄点或红点,就会触发错误。机器人可以轻松到达黄点,因为它们靠近初始位置。然而,绿点和红点更难到达,因为需要找到更精准的路径,或者距离目标太远。
强化学习算法的两大阶段是 探索(exploration)和利用(exploitation) ,演化算法相当于提升了强化学习算法的探索能力,从而得以遍历不同的策略,触及角落中隐藏的bug。这样的策略,其实也相当于一种游戏测试脚本,脚本指导智能体去玩游戏,遍历各种场景和各种互动。
为了实现目标, Wuji 不仅考虑完成任务,还考虑寻找不同的方向,这两种策略相辅相成。比如在迷宫游戏中,完成任务的策略有助于达到一般随机策略难以覆盖的绿点,探索的策略则有助于触及可能不在游戏主线中的红点。
当时这项成果称得上是 业界第一个利用机器学习方法进行游戏测试的工具 ,帮助游戏测试人员发现了大量多人在线游戏中之前未知的bug。相关论文也在软件工程顶级会议 ASE 2019 中获得了 ACM SIGSOFT 杰出论文奖。
部分测试场景示例
8
多智能体系统研究是一个非常复杂的全局优化问题,它不像图像识别、语音生成、文本生成,通常只有固定的少量输入、输出端口,而是有多少智能体,就得有多少的输入、输出。
系统除了要满足全局优化目标,即社会利益最优,还需要考虑每个智能体的利益问题,这就涉及到了公平性,也因此郝建业格外注重这两个方面。 甚至要考虑存在性问题,把多智能体系统类比为神经网络,一个智能体在某些场景下是不能像一个神经元那样被轻易dropout的。映射到真实世界的人类社会,在满足社会、企业利益目标的时候,一个普通人也不该被轻易地剥削或牺牲。
事实上,这一点在斯坦福大学计算机科学名誉教授 Yoav Shoham 于2006年发表的一篇论文中就有提到,即多智能体学习研究的其中一个重要目标——解释现实世界,Yoav Shoham称之为描述性范式。
9
雷锋网特约稿件,未经授权禁止转载。详情见。