您正在使用IE低版浏览器,为了您的雷峰网账号安全和更好的产品体验,强烈建议使用更快更安全的浏览器
此为临时链接,仅用于文章预览,将在时失效
国际 正文
发私信给AI科技评论
发送

1

ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

本文作者:AI科技评论 2016-06-22 10:42
导语:国际机器学习大会上,谷歌DeepMind的主程序员发布论文,探讨AI如何解决不完美信息游戏。

6月19日(美国时间)在纽约举行的国际机器学习大会(ICML)上,来自谷歌、Facebook以及顶尖研究学府的科学家们通过论文和讲座,分享了最尖端的机器学习研究成果。其中,谷歌DeepMind科学家David Silver在讲座“深度增强学习”中分享了深度神经网络在各项实际应用中的算法。虽然David Silver不如DeepMind CEO Demis Hassabis那么为人所知,实际上,他正是DeepMind围棋团队一直雪藏的主程序员。 ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

从左到右:David Silver、Demis Hassabis和围棋冠军李世石。图片来源:BI

David Silver以班级最优成绩从剑桥大学毕业,正是在剑桥他与Demis Hassabis相识,据称也正是Hassabis教会了Silver如何下围棋。毕业后,Silver成立了游戏公司 Elixir 并担任CTO及程序负责人,赢得了一系列科技创新奖项。2004年Silver开始攻读PHD,期间联合引入了初代围棋程序的算法,该算法当时在9 x 9的棋盘打赢人类。Silver从DeepMind创立之初便一直担任顾问,2013年全职加入团队,2014年谷歌收购了DeepMind。今年3月,DeepMind的人工智能算法AlphaGo在19 x 19的标准棋盘上打赢了人类围棋冠军。Hassabis对英国《卫报》说:“我们曾经幻想着今生可以做这样的事情(创造强大的AI),所以,我们19岁的自己如果知道了,应该会感到安心。”

Silver此次ICML的讲座主要探讨应用广泛的增强学习技术。“人工智能的一个主要目标,是创造具有通用目标的代理,能够在众多具有挑战性的任务中高效运行。为实现这一目标,我们需要将增强学习(RL)代理与强大、灵活的表征结合起来。RL的关键概念是利用神经网络来获得这种表征的力量。这场讲座中,我们将介绍一系列深度神经网络用于估值函数、策略或者环境模型的算法。我们将呈现各个领域内最顶尖的研究结果,包括Atari游戏、3D导航任务、持续控制以及围棋。”

讲座中提到,DeepMind的强化学习的不只应用于Atari游戏、扑克和围棋,还包括导航领域中的3D世界和迷宫,控制物理系统中如何进行操作、走路和游泳等动作,还有在用户交互层面的推荐、优化和个人化等等。

今年8月,Demis Hassabis等人工智能技术先驱们将来到雷锋网“人工智能与机器人创新大会”。在此,我们为大家分享David Silver的论文《不完美信息游戏中的深度强化学习自我对战》。本篇论文主要以扑克进行实验,探讨深度强化学习与普通强化学习相比的优势。研究此类游戏不只是可以让程序打赢人类大师,还可以帮助开发算法,应用于更复杂的真实世界环境中,例如机场和网络安全、金融和能源贸易、交通管制和疏导,帮助人们在不完美的信息和高维度信息状态空间中进行决策。深度强化学习不需要依赖人类专家的原有知识,这解决了游戏的可扩展性问题,未来算法可以不依赖成本高昂的人类专家,也不用担心受到偏见等非理性因素的影响,就能帮助决策。论文的另一位作者是伦敦大学学院的研究学生 Johannes Heinrich。

论文摘要

许多真实世界应用可以描述为不完美信息游戏的扩展版本。对于这些挑战巨大的领域,之前的研究主要集中在计算手工抽象出来的纳什均衡。这篇论文中,我们引入第一个可扩展的端到端方法,无需预先具备任何知识,就能学会模拟纳什均衡。我们的方法将虚拟自我对战与深度强化学习结合起来。当应用在德州扑克时,神经虚拟自我对战(NFSP)达到了一种纳什均衡,而普通的强化学习方法则出现了偏离。在限制德州拿住扑克中(一种真实世界规模的扑克游戏),NFSP学会了一种很有竞争力的策略,实现了人类专家的能力和顶尖的方法

1、简介

历史上,游戏一直推动着人工智能和机器学习的进步(Samuel, 1959; Tesauro, 1995; Campbell 等人, 2002; Riedmiller 等人, 2009; Gelly 等人, 2012; Bowling 等人, 2015)。游戏理论将游戏定义为一个冲突区域或者多方的合作(Myerson,1991)。之所以学习比较简单的娱乐游戏,其中一个目的是开发算法,可以扩展到更加复杂的真实世界游戏,例如机场和网络安全、金融和能源贸易、交通管制和疏导(Lambert III 等人, 2005; Nevmyvaka 等人, 2006; Bazzan, 2009; Tambe, 2011; Urieli & Stone, 2014; Durkota 等人, 2015)。大部分这些真实世界游戏都需要进行决策,而决策基于不完美的信息以及高维度的信息状态空间。不幸的是,许多已经应用到经典游戏中的机器学习方法,在信息不完美的游戏中缺少收敛的保证。另一方面,许多游戏理论方法缺少抽取相关模式、并从数据中概况的能力。这让大型游戏的可扩展性有限,除非使用人类专家知识、启发式方法和建模来将该领域抽象化至可控的规模。然而,获取人类专业知识竞猜需要昂贵的资源和时间。此外,人类很容易出现非理性的决策或者假设(Selten, 1990;Ariely & Jones,2008)。这让我们希望开发算法,端到端地学习有用的策略。

这篇论文中我们引入NFSP,一个深度强化学习方法,可以学习模拟不完美信息游戏的纳什均衡。NFSP 代理的学习方法是与自己对战,无需预先具有明确的知识。技术上来说,NFSP 利用神经网络函数模拟,将虚拟自我对战(FSP)(Heinrich 等人, 2015)扩展并实例化。一个 NFSP 代理由两个神经网络和两种记忆组成。强化学习利用与代理同伴一起玩的记忆体验来训练神经网络,预测行为的预期价值。代理自己行为的经验(st,at)储存在一个分开的记忆中,一个监督学习方法利用该记忆来训练神经网络,预测代理自己的平均行为。NFSP 代理可以通过从自己的行为的平均、常规策略和贪婪策略(贪婪策略将预测的估值最大化)中取样,从而小心行事。NFSP 模拟虚拟对战,这是在游戏学习中一种流行的游戏理论模型,在一些经典游戏中收敛至纳什均衡,例如双玩家零和游戏和多玩家潜在博弈。

我们在一个双人零和计算机扑克游戏中实证评估了我们的方法。在这个领域中,目前的游戏理论方法使用启发性方法,将游戏抽象至一个可以驾驭的规模(Zinkevich 等人, 2007; Gilpin 等人, 2007; Johanson 等人,2013)。虽然限制德州拿住扑克(LHE)——一种真实世界规模的扑克游戏——已经可以用目前的计算资源解决(Bowling 等人,2015),大部分其他扑克和真实世界游戏如果不经过抽象化便无法触及。我们的方法不依赖例如抽象化或者其他任何的预先知识。NFSP 代理利用深度强化学习来直接从其与游戏互动的经验中学习。当应用在德州扑克上的时候,NFSP 实现了一种纳什均衡,而普通的强化学习方法出现了偏离。我们还将 NFSP 应用到 LHE,直接从原始输入中学习。NFSP 学会了一种具有竞争力的策略,基于手工抽象化实现了顶尖方法的运行效果。

2、背景

在这个部分,我们展现一个对于强化学习方法、扩展式博弈论表述虚拟自我对战的简短概况。如需更加细节的阐述,我们推荐读者阅读 (Sutton & Barto, 1998), (Myerson, 1991), (Fudenberg, 1998) and (Heinrich 等人, 2015)。

2.1. 强化学习(RL)

强化学习(Sutton & Barto,1998)代理通常从与环境的互动中,学会将预期的未来奖励最大化。环境通常是作为“马尔可夫决策过程”(MDP)进行建模。代理基于策略行动,策略具体说明在MDP的每一个状态中,可行行动的分布。代理的目标是改善自己的策略,从而最大化其收获,是从 t 时间开始,代理累计未来回报的一个随机变量:ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏许多强化学习算法从过渡元组形式的连续“经验”中学习,(st ,at ,rt+1 ,st+1 ),其中 st 是 t 时间的状态,at 是这个状态中选择的行动,rt+1 是其后获得的奖励,st+1 是代理过渡进入的下一个状态。一个普遍的目标是“学习行动价值函数”,ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏定义为在 s 状态、遵循 π 策略、采取 a 行为后预计获得的奖励。如果代理学会自己正在遵循的策略,那么代理的学习是“符合策略”的。在“偏离策略”的情况下,代理从其他代理的经验中学习,或者学会一个其他的策略,例如一个以前的策略。

Q-学习(Watkins & Dayan,1992)是一种流行的偏离策略强化学习方法。它学会贪婪策略,这在每一个状态下采取最高预估值的行动。通过将偏离政策强化学习应用到各自的过度元组,从而将过往的经验储存和回放,这被称为经验回放(Lin,1992)。拟合Q值迭代(FQI)(Ernst 等人, 2005)是一种批量学习方法,用Q-学习来回放经验。神经拟合Q值迭代(NFQ)(Riedmiller,2005)和深度Q网络(DQN)(Mnih 等人,2015)是FQI 的扩展,使用分别带有批量和在线更新的神经网络函数近似。

2.2. 扩展式博弈论表述

扩展式博弈论表述是一种涉及多个玩家的连续互动模型。假设玩家为理性的,每个玩家的目标是最大化自己在游戏中的收获。在不完美信息游戏中,每个玩家至观察到各自的“信息状态”,换句话说,在扑克游戏中,一个玩家只知道他自己的卡片,不知道其他玩家的卡片。每一个玩家选择一个“行为策略”,将信息状态匹配到可选行动的概率分布中。我们假设具有“完美回想能力”的游戏,即,每个玩家目前的信息状态ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏包含玩家信息状态和行动的数列ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏这个数列将玩家带入目前的信息状态。“实现概率”(Von Stengel,1996)ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏决定玩家 i 行为策略 πi 对实现信息状态ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏有利的概率。“策略描述” π = (π1,...,πn) 是所有玩家的策略集合。π-i 指的是, π 中除了 πi 的所有策略。当给出一个固定的策略描述 π-i,基于 π-i,玩家 i 实现最优回报表现的策略称为“最优回应”。一个近似或者 ε-最佳回应,是不超过 ε 的次优回应。“纳什均衡”是一种策略描述,其中每一个玩家的策略对于其他策略来说是一种最优回应。同样的,一个近似或者 ε-纳什均衡是一种 ε-最优的回应。在纳什均衡中,没有哪个玩家在偏离策略的时候能有收获。因此,纳什均衡可以作为一个理性自我对战学习的定点。实际上,纳什均衡是唯一一个理性代理有望在自我对战中收敛的策略描述(Bowie & Veloso,2001)。

2.3. 虚拟自我对战

“虚拟对战”(Brown,1951)是一个从自我对战中学习的游戏理论模型。虚拟玩家选择对应对手平均行为的最优回应。虚拟玩家的平均策略在特定游戏类别中收敛于纳什均衡,例如,双玩家的零和游戏和多玩家潜在博弈(Robinson, 1951; Monderer & Shapley, 1996)。Leslie & Collins (2006)引入了概括化的弱化虚拟对战,具有与普通虚拟对战相似的收敛保证,但是允许近似最优回应和扰动平均策略更新,使其特别适合机器学习。

虚拟对战通常以正则形式定义,这比扩展式博弈论表述要低效得多。Heinrich 等人 (2015) 引入了“全宽度扩展式虚拟对战”(XFP),让虚拟玩家可以行为主义地、扩展式地更新策略,这造成了线性时间和空间的复杂度。一个关键结论是,对于一个正则形式策略的凸组合,ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

我们可以获得一个等同于实现的行为主义策略 δ,方法是将其设定为与对应的实现概率凸组合成比例,

ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

其中ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏是在信息状态 s 中策略的正则化常数。除了定义行为策略中虚拟玩家的全宽度平均策略更新,方程(1)规定了一种从此类策略的凸组合数据库中取样的方法。Heinrich 等人(2015)引入了“虚拟自我对战”(FSP),一种基于样本和机器学习类别的算法,可以近似 XFP。FSP 分别用强化和监督学习代替了最优回应计算和平均策略更新。尤为重要的是,FSP 代理在自我对战中生成自己经验的数据库。每一个代理将其经验过渡元组ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏储存在一个指定用于强化学习的记忆 MRL 中。代理自己行为的经验(st,at)的储存在一个分开的记忆 MSL 中,指定用于监督学习。自我对战取样的设定方式,让代理的强化学习记忆近似一个其他玩家平均策略描述所定义的 MDP 的数据。类似地,代理的监督学习记忆近似代理自己平均策略的数据,可以通过监督分类习得。

3. 神经虚拟自我对战

神经虚拟自我对战(NFSP)是 FSP 的 进化版本,引入了多个扩展,例如神经网络函数近似、蓄水池抽样、预期动态和一个完全基于代理的方法。NFSP 代理与游戏中其他玩家互动,记住自己游戏转换的经验以及自己的行为。NFSP 将这些记忆看做两个适合深度强化学习和监督分类的数据库。代理还特别训练一个神经网络 FQ ,使用偏离政策的强化学习,从数据库 MRL 中预测行为值 Q(s, a)。它产生的神经网络定义代理的近似最优回应策略: β = ε-greedy (FQ),后者选择一个概率为 ε 的随机行为,否则则会选择一个能够最优化预测行为值的行为。NFSP 代理训练一个分开的神经网络 FS,用监督分类在数据 MSL 上模拟自己过去的行为。这个神经网络将状态匹配到行动概率,并定义代理的平均策略 π = FS。游戏中代理从其两项策略 β 和 π 的混合中选择自己的行为。

虽然虚拟玩家通常对于对手的平均策略采取最优回应,在连续时间动态虚拟游戏(Shamma & Arslan,2005)中,玩家基于对手的平均正则策略ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏的短期预测,来选择最优回应。作者显示了这项基于游戏的恰当选择,针对均衡点上虚拟玩家的 η 稳定性。NFSP 使用ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏作为这项预期动态中使用的导数的离散时间近似。注意,ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏是常见离散时间虚拟游戏的正则化更新方向。为了让一个 NFSP 代理计算出近似最优回应 βi,对于其对手的预期平均策略描述ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏代理迭代性地评估和最大化其行为值ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏实现的方法可以是基于和对手的预期策略 δ-i 游戏的经验,进行偏离策略的强化学习,即,Q-学习或者 DQN。为确保代理的强化学习记忆 MRL 包含这种经验,NFSP 要求所有代理从ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏中选择他们的行为,其中 η ∈ R 被称为“预期参数”。

虚拟游戏通常追踪玩家在游戏中已选的正则形式最优回应策略的平均值ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏。Heinrich 等人(2015)提出使用取样和机器学习来生成数据,学习正则形式策略拓展形式的凸组合。例如,我们可以生成一组数据ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏的扩展形式,方法是从整个游戏时间中取样,在凸组合中使用ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏与其权重 1/T 成比例。NFSP 使用蓄水池取样(Vitter,1985;Osborne 等人,2014)来记忆自己平均最优回应的经验。代理的监督学习记忆 MSL 是一个蓄水池,只有当它遵循近似最优回应策略 β 的时候才增加经验。NFSP 代理常规性地训练自己的平均策略网络 π = FS,与自己存储在自己监督学习记忆中的平均行为相匹配,例如通过最优化过去行为的日志概率。算法(1)呈现了使用 DQN 进行强化学习的 NFSP。

ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

算法1:使用 DQN 进行强化学习的 NFSP。

4、实验

我们在德州扑克(Southey 等人,2005)和限制德州拿住扑克中评估 NFSP 和相关算法。我们大部分的实验学会策略描述的可利用性。在一个双玩家零和游戏中,一项策略描述的可利用性定义为,最优回应描述可以获得的期望平均回报。2δ 的可利用性至少是一个 δ-纳什均衡。

4.1. XFP 的强度

要理解函数近似如何与 FSP 互动,我们以一些简单实验开始,模拟近似,并从全宽度算法 XFP 中获取错误样本。首先,我们探索当用一个靠近梯度下降的增量平均过程代替 XFP 中使用的完美平均,会有什么结果。然后,我们探索当用一个带 ε 误差的近似代替 XFP 中使用的同一个查表法,会有什么结果。

ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

图1:定步长对于 LHE 游戏中全宽度虚拟对战表现的影响。

图1显示了带有默认值 1/T 和策略更新定步长的 XFP 的表现。我们看见渐进提高了,但是针对更小步长的最初表现变低了。对于定步长,表现似乎是达到平稳、而非偏离。使用蓄水池取样可以实现高效的定步长,为 1/T。但是,结果显示指数平均的蓄水池取样同样可行,因为指数平均过往记忆会近似对应于使用一个定步长。

定步长为1的 XFP等同于一个全宽度迭代最优回应算法。虽然在有限完美信息双玩家零和游戏中这个算法收敛于纳什均衡,结果显示,在不完美信息中这就不能成立了。Yakovenko 等人(2016)引入的扑克-CNN 算法存储少量过往策略,基于这些策略迭代性地计算新策略。代替那个集合中的策略类似于更新一个具有很大定步长的平均策略。这有可能导致类似图1中显示的问题。

ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

图2:当 LHE 游戏在最优回应计算中加入均匀随机噪音,XFP 的表现。

我们的 NFSP 代理在他们的策略中加入随机探索,使用噪音随机梯度来学习行动价值。因此,我们研究了在最优回应计算中加入随机噪音的影响,XFP 通过动态编程来运行最优回应计算。在逆向归纳法的每一步,我们传回一个带有概率 ε 的均匀随机行动的值,否则则传回最佳行动的值。图2显示出,增加噪音时表现清一色地下降。但是,表现仍保持稳定,对于所有噪音等级来说都持续改善。

4.2. NFSP的收敛

我们实证研究了在 LHE 游戏中 NFSP 收敛至纳什均衡。我们还研究了去除或改变一些 NFSP 的组成部分是否会打破收敛。

我们的一项目标,是将对过往知识的依赖性最小化。因此,我们希望定义一个扑克游戏中信息状态的目标编码。与其他计算机扑克的研究不同(Zinkevich 等人, 2007; Gilpin 等人, 2007; Johanson 等人, 2013),我们不进行任何高层级特征的工程。扑克游戏通常包含很多轮。在每一轮,新卡片发给玩家。我们将每一轮的卡片用一个“n 个中的第 k 个”编码来表征,例如,当 LHE 有一叠52张卡片,第二轮发出三张新卡。这样,这一轮的编码就使用长度为52的矢量和三个设为1的元素,其余元素设为0。在 LHE 扑克游戏中,玩家通常有3种可选的行为,即 {弃牌、根注、加注} 。注意,根据情景而定,跟注和加注可以分别称为“让牌”和“押注”。押注限制在每轮固定数量的加注之内。这样,我们可以将押注历史表征为一个4维度的张量,即 {玩家、轮数、加注数量、采取行动} 。也就是说,单挑 LHE 游戏中包含2个玩家、4轮、每轮0-4次加注和3个行动。这样,我们可以将一个 LHE 押注历史表征为 2 x 4 x 5 x 3 张量。在单挑游戏中,我们不需要编码弃牌行为,因为如果一方放弃游戏就结束了。这样,我们可以将4维张量扁平化,成为一个长度为80的矢量。将4轮的卡牌都联接起来,我们就可以将一个 LHE 的信息状态编码为一个长度为288的矢量。相似地,一个 LHE 的信息状态可以编码为一个长为30的矢量,因其包含6种卡片以及3个重复卡片、2轮、每轮0-2次加注以及3次行动。

要实现 LHE 中的学习,我们将 NFSP 手动校准为一个完全联接的神经网络,带有1个隐含层、包含63个神经元和线性激活。然后,我们重复各种具有相同参数的神经架构的实验。我们特别设置记忆大小为200K,MRL 和 MSL 分别为2M。MRL 的功能是一个环形缓冲器,包含一个最近的经验。MSL 用蓄水池取样更新。强化学习率和监督学习率分别设置为为 0.1 和 0.005,两者都使用随机梯度下降(SGD),没有神经网络随机最优化的趋势。每一个代理进行3次随机梯度更新,游戏中每128步、每个神经网络中最小批次数量为128。DQN 算法的目标网络每300次更新就重新调整。NFSP 的预期参数设置为 η = 0.1。ε-贪婪策略的探索从 0.06 开始,下降到0,与迭代次数的逆平方根成比例。

ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

图3:LHE 游戏中的 NFSP 的学习表现。

图3显示了对于各种网络架构, NFSP 趋近纳什均衡。我们观察到随着网络数量的增加,表现也清一色地增加。NFSP 实现了0.06的利用性,而全宽度 XFP 通常在1000轮全宽度迭代才能实现。

ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

图4:通过去除必须的 NFSP 组成部分,打破 LHE 游戏中的学习表现。

为了研究 NSFP 各种组成部分的相关度,也就是说,蓄水池取样和期望动态,我们进行了一个分离他们效果的实验。图4显示,这些变动导致表现下降。特别是使用固定大小的滑动窗口来储存代理自己行为的经验,会导致偏离。对于一个0.5的高期望参数,NFSP 的表现进入了停滞。最终,使用指数平均蓄水池取样进行监督学习记忆更新,导致了噪音表现。

4.3. 与DQN比较

之前已有多个稳定算法提出过用于深度强化学习,尤其是 DQN 算法(Mnih 等人,2015)。但是,这些算法的实证稳定性之前只在单一代理、完美(或接近完美)信息 MDP 中建立过。这里,我们研究与 NFSP 相比,在多代理、信息不完美游戏中的 DQN 稳定性。

ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

图5:在 LHE 游戏中比较 DQN 的表现。

DQN 学会一种决定论的贪婪策略。这在 MDP 中足够进行最优行为,算法就是为此而设计的。不过,在信息不完美游戏通常要求最优行为的随机策略。这样,除了 DQN 的 ε-贪婪策略,我们将其行为存储在一个监督学习记忆 MSL 中,并学习其平均行为。这项平均策略不影响 DQN 的实施行为,因为它从来不会被执行。我们通过使用带有期望参数 η = 1 的 NFSP,来实施这个 DQN 变量。我们将 DQN 大部分参数设置为与之前部分实验中的 NFSP 相同。这是为了让监督学习参数不直接影响 DQN 的表现。我们用以下所有参数的组合来训练 DQN:学习比例 {0.2,0.1,0.05},衰减探索开始于 {0.06,012},增强学习记忆 {2m蓄水池,2m滑动窗口}。然后,我们选择 DQN 表现最优的结果,将其与之前部分实验中的 NFSP 表现相比较。DQN 在学习比例为0.1、探索从0.12开始和滑动窗口记忆为2m的时候,实现其最佳表现结果。

图5显示,DQN的决定论策略是高度可利用的,这是可以预见的,因为信息不完美游戏通常要求随机策略。DQN 的平均行为也没有趋近纳什均衡。这值得注意,因为 DQN 将其经验存储在一个回放记忆中,因此会高效地学会对手的平均行为,只要其回放记忆足够大,可以对它进行追踪。这与虚拟对战很像。但是,因为 DQN 代理在自我对战中使用 ε-贪婪策略,它们的经验随着时间高度相关,集中在一个状态子集。我们相信这是 NFSP 在我们试验中表现更好的主要原因。NFSP 代理在自我对战中使用一种改变更慢的平均策略。这样,它们的经验改变更慢,导致它们的记忆中包含更稳定的数据分布。这会帮助它们训练神经网络,并适应彼此。其他常见的强化学习方法都被证明在扑克游戏中具有类似的停滞表现(Ponsen 等人,2011; Heinrich & Silver, 2015)。

4.4. 限制德州拿住 (LHE)

我们将 NFSP 应用于非常流行的 LHE 游戏。2008年,一个计算机程序第一次在公开竞赛中打败了人类 LHE 玩家,从此现代计算机代理被广泛认为实现了超人表现(Newall,2013)。这种游戏由 Bowling等人(2015)根本上解决。我们用 SmooCT 来评估我们的代理,这是一个在2014年年度计算机扑克竞赛(ACPC)中获得了三项银牌的 Smooth UCT (Heinrich & Silver,2015)代理。学习表现以 mbb/h 来衡量,换句话说,在每一手最开始的时候玩家大盲注的千分之一。

我们手动校准了 NFSP,尝试了9种配置。我们用以下的参数实现了最优表现。神经网络完全联接,有4个隐藏层,分别有1024、512、1024和512个具有线性激活的神经元。MRL和MSL的记忆容量分别设定为600k和30m。MRL作为环形缓冲器,包含一个近期经验。MSL用指数平均的蓄水池取样(Osborne等人,2014)更新,用最低概率0.25代替MSL中的条目。我们使用没有强化学习和监督学习趋势的 SGD,将学习比例分别设置为0.1和0.01。每一个代理进行2次随机梯度更新,游戏中每256步、每个网络的最小批次大小为256。DQN 算法的目标网络是每1000次更新就重新调整。NFSP的预期参数设置为 η = 0.1。ε-贪婪策略的探索从0.08开始,衰退至0,比在 LHE 中更慢。除了 NFSP 的主要平均策略描述,我们还评估了最优回应和贪婪平均策略,它们决定论地分别选择最大化预期行动值或者概率的行动。

ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

图6:与 SmooCT 对战的表现。每次评估的标准误差小于 10 mbb/h。

为了在单挑 LHE 中提供一些胜率的直觉,永远弃牌的玩家会损失 750 mbb/h,人类专家玩家在在线高风险游戏中通常达到40-60 mbb/h 的预期胜率。类似的,在2014 ACPC中,表现前一半的计算机代理自己实现了最高 60 mbb/h 的预期胜率。在训练中,我们基于 SmooCT 周期性地评估 NFSP 的表现,每一个都玩25000手。图6呈现了 NFSP 的学习表现。NFSP 的平均和贪婪平均策略描述显示了一个稳定、相对统一的表现改善,并分别实现了大约-50 mbb/h 和-20 mbb/h 的胜率。最优回应策略描述在每次表现中体现了更多的噪音,大部分在 -50 到 0 mbb/h 的范围内。我们还基于2014 ACPC中的前三名,评估了最终贪婪平均策略。表格1呈现了结果。

ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

表格1

5. 相关研究

依赖人类专家知识可能会很昂贵,而且如果知识是次优的,可能会受到人类偏见和限制的影响。但是,许多已经应用在游戏中的方法都依赖人类专家的知识。深蓝在象棋中使用人类制造的评估函数(Campbell等人,2002)。在计算机围棋中,Maddison等人(2015)和Clark & Storkey (2015)用人类专家下棋的数据来训练深度神经网络。在计算机扑克中,目前的游戏理论方法使用启发式方法来理解卡片强度,从而将游戏抽象至可以驾驭的规模(Zinkevich等人, 2007; Gilpin等人, 2007; Johanson等人,2013)。Waugh等人(2015)最近将其中一种方法与函数近似相结合。然而,他们的全宽度算法必须暗中推导每一次迭代中的所有信息状态,这在大的领域来说过于昂贵。与之相比,NFSP 专注在基于样本的强化学习设定,其中游戏的状态不需要全部列举,学习者甚至不需要有一个游戏动态的模型。

许多游戏中的成功应用依赖本地搜索(Campbell等人,2002;Browne等人,2012)。本地搜索算法在游戏中,实时、有效地计划决策,例如通过蒙特卡洛模拟或者有限深度逆向归纳法。但是,常见的基于模拟的本地搜索算法应用在信息不完美的扑克游戏中时,已经证实会偏离(Ponsen等人,2011;Heinrich & Silver,2015)。而且,即便是游戏理论方法在信息不完美游戏中进行本地规划时,通常也没法实现不可利用的行为(Burch等人,2014;Ganzfried & Sandholm,2015;Lisy等人,2015)。本地搜索的另一个问题是,如果没有注入原有知识来引导搜索,实时运行的成本有可能非常巨大。这引发了如何获得这种原有知识的问题。Silver等人(2016)用人类专家数据训练了卷积神经网络,然后使用一个自我对战强化学习过程来进一步优化这些网络。通过使用这项神经网络来引导高性能本地搜索,他们战胜了围棋大师。在这项研究中,我们不使用任何实时本地搜索来评估我们的代理。如果可以开发针对信息不完美游戏的本地搜索方法,NFSP 训练的策略可以是引导搜索的一个好选择。

纳什均衡是理性代理可以在自我对战中有望收敛的唯一策略描述(Bowling & Veloso,2001)。TD-Gammon(Tesauro,1995)是一个世界级别的西洋双陆棋代理,它的主要组成部分是一个用自我对战强化学习训练的神经网络。虽然其算法基于临时差异学习,在双玩家、信息完美的零和游戏中是可行的,可是在不完美游戏中总体来说不能收敛。DQN(Mnih等人,2015)结合了临时差异学习、经验回放和深度神经网络函数近似。它在大部分Atari游戏中实现了人类等级的表现,从原始感觉输入中学习。但是,这些Atari游戏的设定是单一代理环境,潜在对手固定,并由Atari模拟器控制。我们的实验显示,DQN 代理在 LHE 游戏中没法实现纳什均衡,其中玩家允许进行动态适应。Yakovenko等人(2016)在计算机扑克对战中训练了深度神经网络,包括两个在人类中非常流行的扑克游戏。他们的网络与基于启发式方法和简单的计算机程相比表现更强。人类专家玩家可以超越他们的代理,虽然其样本大小不具有统计学意义。他们的方法在现实或理论中是否会收敛是个未知数。与之对比,我们实证证明了 NFSP 在 LHE 游戏中收敛至近似纳什均衡。而且,我们的方法是有原则的,是基于扩展式博弈论表述中的虚拟对战理论。

6、结论

我们引入了 NFSP,第一个端到端深度强化学习方法,在不完美信息游戏中以自我对战学习近似纳什均衡。NFSP 解决三个问题。

首先,NFSP 代理学习不需要具备原有知识。

第二,他们不依赖于实时本地搜索。

第三,他们在自我对战中收敛至近似纳什均衡。我们的实证结果提供了以下收获:虚拟游戏的表现随着各种近似错误优雅地衰退;NFSP 在小扑克游戏中能可靠地收敛于近似纳什均衡,而 DQN 的贪婪和平均策略不能;NFSP 在真实世界规模的信息不完美游戏中,从零学会一种有竞争力的策略,不需要使用明确的原有知识。

在这项研究中,我们专注于信息不完美的双玩家零和游戏。但是,虚拟对战在合作性的潜在游戏中,也能保证收敛至纳什均衡。因此我们可以看到,NFSP 也可以成功应用于这些游戏。而且,连续动作强化学习的最近进展(Lillicrap等人,2015)可以让 NFSP 应用于连续动作游戏,这是目前的游戏理论方法没法直接解决的问题。

via ICML

ICML论文|阿尔法狗CTO讲座: AI如何用新型强化学习玩转围棋扑克游戏

雷峰网原创文章,未经授权禁止转载。详情见转载须知

分享:
相关文章
当月热门文章
最新文章
请填写申请人资料
姓名
电话
邮箱
微信号
作品链接
个人简介
为了您的账户安全,请验证邮箱
您的邮箱还未验证,完成可获20积分哟!
请验证您的邮箱
立即验证
完善账号信息
您的账号已经绑定,现在您可以设置密码以方便用邮箱登录
立即设置 以后再说