在各种策略中，学会对任何混合物进行最佳作用是竞争游戏中重要的实践兴趣。在本文中，我们提出了同时满足两个Desiderata的单纯形式：i）学习以单个条件网络为代表的战略性不同的基础政策；ii）使用同一网络，通过基础策略的单纯形式学习最佳反应。我们表明，由此产生的条件策略有效地包含了有关对手的先前信息，从而在具有可拖动最佳响应的游戏中几乎可以针对任意混合策略的最佳回报。我们验证此类政策在不确定性下表现出色，并在测试时使用这种灵活性提供了见解。最后，我们提供的证据表明，对任何混合政策学习最佳响应是战略探索的有效辅助任务，这本身可以导致更多的性能人群。
translated by 谷歌翻译
在竞争激烈的两种环境中，基于\ emph {double oracle（do）}算法的深度强化学习（RL）方法，例如\ emph {policy space响应oracles（psro）}和\ emph {任何时间psro（apsro）}，迭代地将RL最佳响应策略添加到人群中。最终，这些人口策略的最佳混合物将近似于NASH平衡。但是，这些方法可能需要在收敛之前添加所有确定性策略。在这项工作中，我们介绍了\ emph {selfplay psro（sp-psro）}，这种方法可在每次迭代中的种群中添加大致最佳的随机策略。SP-PSRO并不仅对对手的最少可剥削人口混合物添加确定性的最佳反应，而是学习了大致最佳的随机政策，并将其添加到人群中。结果，SPSRO从经验上倾向于比APSRO快得多，而且在许多游戏中，仅在几次迭代中收敛。
translated by 谷歌翻译
2020-06-08
深度加强学习（RL）的最新进展导致许多2人零和游戏中的相当大的进展，如去，扑克和星际争霸。这种游戏的纯粹对抗性质允许概念上简单地应用R1方法。然而，现实世界的设置是许多代理商，代理交互是复杂的共同利益和竞争方面的混合物。我们认为外交，一个旨在突出由多种代理交互导致的困境的7人棋盘游戏。它还具有大型组合动作空间和同时移动，这对RL算法具有具有挑战性。我们提出了一个简单但有效的近似最佳响应操作员，旨在处理大型组合动作空间并同时移动。我们还介绍了一系列近似虚构游戏的政策迭代方法。通过这些方法，我们成功地将RL申请到外交：我们认为我们的代理商令人信服地令人信服地表明，游戏理论均衡分析表明新过程产生了一致的改进。
translated by 谷歌翻译
Researchers have demonstrated that neural networks are vulnerable to adversarial examples and subtle environment changes, both of which one can view as a form of distribution shift. To humans, the resulting errors can look like blunders, eroding trust in these agents. In prior games research, agent evaluation often focused on the in-practice game outcomes. While valuable, such evaluation typically fails to evaluate robustness to worst-case outcomes. Prior research in computer poker has examined how to assess such worst-case performance, both exactly and approximately. Unfortunately, exact computation is infeasible with larger domains, and existing approximations rely on poker-specific knowledge. We introduce ISMCTS-BR, a scalable search-based deep reinforcement learning algorithm for learning a best response to an agent, thereby approximating worst-case performance. We demonstrate the technique in several two-player zero-sum games against a variety of agents, including several AlphaZero-based agents.
translated by 谷歌翻译
在解决双球员零和游戏时，多代理强化学习（MARL）算法通常会在每次迭代时创造代理人群，在每次迭代时，将被发现为对对手人口对混合的最佳响应。在这样的过程中，“遵循”（即对手混合物）和“如何击败它们”（即寻找最佳响应）的更新规则是由手动开发的游戏理论原则基础，如虚构的游戏和双倍甲骨文。在本文中，我们介绍了一种新颖的框架 - 神经自动课程（NAC） - 利用元梯度下降来自动化学习更新规则的发现，而无明确的人类设计。具体而言，我们通过优化子程序参数通过神经网络和最佳响应模块参数化对手选择模块，并通过与游戏引擎的交互仅更新其参数，其中播放器旨在最大限度地减少其利用性。令人惊讶的是，即使没有人类的设计，发现的Marl算法也可以通过基于最先进的人口的游戏，在技能游戏，可微分的乐透，不转化的混合物游戏中实现竞争或更好的性能，实现竞争或更好的性能。迭代匹配的便士和kuhn扑克。此外，我们表明NAC能够从小型游戏到大型游戏，例如Kuhn Poker培训，在LEDUC扑克上表现优于PSRO。我们的工作激发了一个未来的未来方向，以完全从数据发现一般的Marl算法。
translated by 谷歌翻译
离线增强学习（离线RL）是一个新兴领域，由于其能够从早期收集的数据集中学习行为，该领域最近开始在各个应用领域中引起关注。当与环境进一步交互（计算或其他方式），不安全或完全不可行时，必须使用记录数据。离线RL被证明非常成功，为解决以前棘手的现实世界问题铺平了道路，我们旨在将此范式推广到多代理或多人游戏设置。由于缺乏标准化数据集和有意义的基准，因此在这一领域进行的研究很少，因为进展受到阻碍。在这项工作中，我们将术语“离线平衡发现（OEF）”创造，以描述该区域并构建多个数据集，这些数据集由使用多种既定方法在各种游戏中收集的策略组成。我们还提出了一种基准方法 - 行为克隆和基于模型的算法的合并。我们的两种基于模型的算法 - OEF-PSRO和OEF-CFR - 是在离线学习的背景下，广泛使用的平衡发现算法深入CFR和PSRO的适应。在经验部分中，我们评估了构造数据集上基准算法的性能。我们希望我们的努力可以帮助加速大规模平衡发现的研究。数据集和代码可在https://github.com/securitygames/oef上获得。
translated by 谷歌翻译
我们研究多个代理商在多目标环境的同时学习的问题。具体来说，我们考虑两种药剂重复播放一个多目标的正常形式的游戏。在这样的游戏，从联合行动所产生的收益都向量值。以基于效用的方法，我们假设效用函数存在映射向量标公用事业和考虑旨在最大限度地提高预期收益载体的效用代理。作为代理商不一定知道他们的对手的效用函数或策略，他们必须学会互动的最佳策略对方。为了帮助代理商在适当的解决办法到达，我们介绍四种新型偏好通信协议双方的合作以及自身利益的沟通。每一种方法描述了一个代理在他们的行动以及如何另一代理响应通信偏好的特定协议。这些协议是一组对不沟通基线代理5个标杆游戏随后对其进行评估。我们发现，偏好通信可以彻底改变学习的过程，并导致其没有在此设置先前观测环纳什均衡的出现。另外，还要在那里代理商必须学会当通信的通信方案。对于与纳什均衡游戏的代理，我们发现通信可以是有益的，但很难知道什么时候剂有不同的最佳平衡。如果不是这种情况，代理变得冷漠通信。在游戏没有纳什均衡，我们的结果表明，整个学习率的差异。当使用更快的学习者，我们观察到明确的沟通，在50％左右的时间变得越来越普遍，因为它可以帮助他们在学习的妥协联合政策。较慢的学生保留这种模式在较小的程度，但显示增加的冷漠。
translated by 谷歌翻译
In many real-world settings agents engage in strategic interactions with multiple opposing agents who can employ a wide variety of strategies. The standard approach for designing agents for such settings is to compute or approximate a relevant game-theoretic solution concept such as Nash equilibrium and then follow the prescribed strategy. However, such a strategy ignores any observations of opponents' play, which may indicate shortcomings that can be exploited. We present an approach for opponent modeling in multiplayer imperfect-information games where we collect observations of opponents' play through repeated interactions. We run experiments against a wide variety of real opponents and exact Nash equilibrium strategies in three-player Kuhn poker and show that our algorithm significantly outperforms all of the agents, including the exact Nash equilibrium strategies.
translated by 谷歌翻译
哈纳比（Hanabi）是一款合作游戏，它带来了将其他玩家建模到最前沿的问题。在这个游戏中，协调的一组玩家可以利用预先建立的公约发挥出色的效果，但是在临时环境中进行比赛需要代理商适应其伴侣的策略，而没有以前的协调。在这种情况下评估代理需要各种各样的潜在伙伴人群，但是到目前为止，尚未以系统的方式考虑代理的行为多样性。本文提出了质量多样性算法作为有前途的算法类别，以生成多种人群为此目的，并使用MAP-ELITE生成一系列不同的Hanabi代理。我们还假设，在培训期间，代理商可以从多样化的人群中受益，并实施一个简单的“元策略”，以适应代理人的感知行为利基市场。我们表明，即使可以正确推断其伴侣的行为利基市场，即使培训其伴侣的行为利基市场，这种元策略也可以比通才策略更好地工作，但是在实践中，伴侣的行为取决于并干扰了元代理自己的行为，这表明是一条途径对于未来的研究，可以在游戏过程中表征另一个代理商的行为。
translated by 谷歌翻译
游戏历史悠久的历史悠久地作为人工智能进步的基准。最近，使用搜索和学习的方法在一系列完美的信息游戏中表现出强烈的表现，并且使用游戏理论推理和学习的方法对特定的不完美信息扑克变体表示了很强的性能。我们介绍游戏玩家，一个通用算法，统一以前的方法，结合导游搜索，自助学习和游戏理论推理。游戏播放器是实现大型完美和不完美信息游戏中强大实证性能的第一个算法 - 这是一项真正的任意环境算法的重要一步。我们证明了游戏玩家是声音，融合到完美的游戏，因为可用的计算时间和近似容量增加。游戏播放器在国际象棋上达到了强大的表现，然后击败了最强大的公开可用的代理商，在头上没有限制德克萨斯州扑克（Slumbot），击败了苏格兰院子的最先进的代理人，这是一个不完美的信息游戏，说明了引导搜索，学习和游戏理论推理的价值。
translated by 谷歌翻译
我们介绍了DeepNash，这是一种能够学习从头开始播放不完美的信息游戏策略的自主代理，直到人类的专家级别。 Stratego是人工智能（AI）尚未掌握的少数标志性棋盘游戏之一。这个受欢迎的游戏具有$ 10^{535} $节点的巨大游戏树，即，$ 10^{175} $倍的$倍于GO。它具有在不完美的信息下需要决策的其他复杂性，类似于德克萨斯州Hold'em扑克，该扑克的游戏树较小（以$ 10^{164} $节点为单位）。 Stratego中的决策是在许多离散的动作上做出的，而动作与结果之间没有明显的联系。情节很长，在球员获胜之前经常有数百次动作，而Stratego中的情况则不能像扑克中那样轻松地分解成管理大小的子问题。由于这些原因，Stratego几十年来一直是AI领域的巨大挑战，现有的AI方法几乎没有达到业余比赛水平。 Deepnash使用游戏理论，无模型的深钢筋学习方法，而无需搜索，该方法学会通过自我播放来掌握Stratego。 DeepNash的关键组成部分的正则化NASH Dynamics（R-NAD）算法通过直接修改基础多项式学习动力学来收敛到近似NASH平衡，而不是围绕它“循环”。 Deepnash在Stratego中击败了现有的最先进的AI方法，并在Gravon Games平台上获得了年度（2022年）和历史前3名，并与人类专家竞争。
translated by 谷歌翻译
本文提出了用于学习两人零和马尔可夫游戏的小说，端到端的深钢筋学习算法。我们的目标是找到NASH平衡政策，这些策略不受对抗对手的剥削。本文与以前在广泛形式的游戏中找到NASH平衡的努力不同，这些游戏具有树结构的过渡动态和离散的状态空间，本文着重于具有一般过渡动态和连续状态空间的马尔可夫游戏。我们提出了（1）NASH DQN算法，该算法将DQN与nash finding subroutine集成在一起的联合价值函数； （2）NASH DQN利用算法，该算法还采用了指导代理商探索的剥削者。我们的算法是理论算法的实用变体，这些变体可以保证在基本表格设置中融合到NASH平衡。对表格示例和两个玩家Atari游戏的实验评估证明了针对对抗对手的拟议算法的鲁棒性，以及对现有方法的优势性能。
translated by 谷歌翻译
Monte Carlo Tree Search (MCTS) is a recently proposed search method that combines the precision of tree search with the generality of random sampling. It has received considerable interest due to its spectacular success in the difficult problem of computer Go, but has also proved beneficial in a range of other domains. This paper is a survey of the literature to date, intended to provide a snapshot of the state of the art after the first five years of MCTS research. We outline the core algorithm's derivation, impart some structure on the many variations and enhancements that have been proposed, and summarise the results from the key game and non-game domains to which MCTS methods have been applied. A number of open research questions indicate that the field is ripe for future work.
translated by 谷歌翻译
具有很多玩家的非合作和合作游戏具有许多应用程序，但是当玩家数量增加时，通常仍然很棘手。由Lasry和Lions以及Huang，Caines和Malham \'E引入的，平均野外运动会（MFGS）依靠平均场外近似值，以使玩家数量可以成长为无穷大。解决这些游戏的传统方法通常依赖于以完全了解模型的了解来求解部分或随机微分方程。最近，增强学习（RL）似乎有望解决复杂问题。通过组合MFGS和RL，我们希望在人口规模和环境复杂性方面能够大规模解决游戏。在这项调查中，我们回顾了有关学习MFG中NASH均衡的最新文献。我们首先确定最常见的设置（静态，固定和进化）。然后，我们为经典迭代方法（基于最佳响应计算或策略评估）提供了一个通用框架，以确切的方式解决MFG。在这些算法和与马尔可夫决策过程的联系的基础上，我们解释了如何使用RL以无模型的方式学习MFG解决方案。最后，我们在基准问题上介绍了数值插图，并以某些视角得出结论。
translated by 谷歌翻译
当今许多大型系统的设计，从交通路由环境到智能电网，都依赖游戏理论平衡概念。但是，随着$ n $玩家游戏的大小通常会随着$ n $而成倍增长，标准游戏理论分析实际上是不可行的。最近的方法通过考虑平均场游戏，匿名$ n $玩家游戏的近似值，在这种限制中，玩家的数量是无限的，而人口的状态分布，而不是每个单独的球员的状态，是兴趣。然而，迄今为止研究最多的平均场平衡的平均场nash平衡的实际可计算性通常取决于有益的非一般结构特性，例如单调性或收缩性能，这是已知的算法收敛所必需的。在这项工作中，我们通过开发均值相关和与粗相关的平衡的概念来研究平均场比赛的替代途径。我们证明，可以使用三种经典算法在\ emph {ash All Games}中有效地学习它们，而无需对游戏结构进行任何其他假设。此外，我们在文献中已经建立了对应关系，从而获得了平均场 - $ n $玩家过渡的最佳范围，并经验证明了这些算法在简单游戏中的收敛性。
translated by 谷歌翻译
DeepMind的游戏理论与多代理团队研究多学科学习的几个方面，从计算近似值到游戏理论中的基本概念，再到在富裕的空间环境中模拟社会困境，并在困难的团队协调任务中培训3-D类人动物。我们小组的一个签名目的是使用DeepMind在DeepMind中提供的资源和专业知识，以深入强化学习来探索复杂环境中的多代理系统，并使用这些基准来提高我们的理解。在这里，我们总结了我们团队的最新工作，并提出了一种分类法，我们认为这重点介绍了多代理研究中许多重要的开放挑战。
translated by 谷歌翻译
强大的增强学习（RL）考虑了在一组可能的环境参数值中最坏情况下表现良好的学习政策的问题。在现实世界环境中，选择可靠RL的可能值集可能是一项艰巨的任务。当指定该集合太狭窄时，代理将容易受到不称职的合理参数值的影响。如果规定过于广泛，则代理商将太谨慎。在本文中，我们提出了可行的对抗性鲁棒RL（FARR），这是一种自动确定环境参数值集的方法。 Farr隐式将可行的参数值定义为代理可以在足够的培训资源的情况下获得基准奖励的参数值。通过将该问题作为两人零和游戏的配方，Farr共同学习了对参数值的对抗分布，并具有可行的支持，并且在此可行参数集中进行了强大的策略。使用PSRO算法在这款FARR游戏中找到近似的NASH平衡，我们表明，接受FARR训练的代理人对可行的对抗性参数选择比现有的minimax，domain randanmization，域名和遗憾的目标更强大控制环境。
translated by 谷歌翻译
We study the problem of training a principal in a multi-agent general-sum game using reinforcement learning (RL). Learning a robust principal policy requires anticipating the worst possible strategic responses of other agents, which is generally NP-hard. However, we show that no-regret dynamics can identify these worst-case responses in poly-time in smooth games. We propose a framework that uses this policy evaluation method for efficiently learning a robust principal policy using RL. This framework can be extended to provide robustness to boundedly rational agents too. Our motivating application is automated mechanism design: we empirically demonstrate our framework learns robust mechanisms in both matrix games and complex spatiotemporal games. In particular, we learn a dynamic tax policy that improves the welfare of a simulated trade-and-barter economy by 15%, even when facing previously unseen boundedly rational RL taxpayers.
translated by 谷歌翻译
2022-07-11
事实证明，加固学习（RL）的自适应课程有效地制定了稳健的火车和测试环境之间的差异。最近，无监督的环境设计（UED）框架通用RL课程以生成整个环境的序列，从而带来了具有强大的Minimax遗憾属性的新方法。在问题上，在部分观察或随机设置中，最佳策略可能取决于预期部署设置中环境的基本真相分布，而课程学习一定会改变培训分布。我们将这种现象形式化为课程诱导的协变量转移（CICS），并描述了其在核心参数中的发生如何导致次优政策。直接从基本真相分布中采样这些参数可以避免问题，但阻碍了课程学习。我们提出了Samplr，这是一种Minimax遗憾的方法，即使由于CICS偏向基础培训数据，它也优化了基础真相函数。我们证明并验证了具有挑战性的领域，我们的方法在基础上的分布下保留了最佳性，同时促进了整个环境环境的鲁棒性。
translated by 谷歌翻译
零和游戏中的理想策略不仅应授予玩家的平均奖励，不少于NASH均衡的价值，而且还应在次优时利用（自适应）对手。尽管马尔可夫游戏中的大多数现有作品都专注于以前的目标，但我们是否可以同时实现这两个目标仍然开放。为了解决这个问题，这项工作在马尔可夫游戏中与对抗对手进行了无重组学习，当时与事后最佳的固定政策竞争时。沿着这个方向，我们提出了一组新的正面和负面结果：当每个情节结束时对手的政策被揭示时，我们提出了实现$ \ sqrt {k} $的新的有效算法 - 遗憾的是（遗憾的是） 1）基线政策类别很小或（2）对手的政策类别很小。当两种条件不正确时，这与指数下限相辅相成。当未揭示对手的政策时，即使在最有利的情况下，当两者都是正确的情况下，我们也会证明统计硬度结果。我们的硬度结果比仅涉及计算硬度或需要进一步限制算法的现有硬度结果要强得多。
translated by 谷歌翻译