标准的游戏理论解答概念,纳什均衡假设所有球员都表现得合理。如果我们遵循纳什均衡和对手是非理性的(或遵循不同的纳什均衡的策略),那么我们可能会获得极低的回报。另一方面,Maximin策略假定所有反对代理都在播放以最大限度地减少我们的收益(即使它不是最佳利益),并确保最大可能的最坏情况,但导致非常保守的戏剧。我们提出了一种新的解决方案概念,称为安全均衡,模拟对手的行为与指定概率的表现合理,并且潜在的任意表现在剩下的概率上。我们证明所有战略形式游戏中存在安全均衡(对于合理性参数的所有可能值),并证明其计算是PPAD-HARD。我们提出了用于计算2和$ N $ -Player游戏中的安全均衡的精确算法,以及可缩放的近似算法。
translated by 谷歌翻译
基于二次约束可行性计划制定,我们描述了一种用于计算多人普通和游戏中的NASH均衡的新完整算法。我们证明,算法比先前研究的几个游戏类上的现有最快完整算法速度快得显着更快,其运行时间甚至优于最佳的不完整算法。
translated by 谷歌翻译
While Nash equilibrium has emerged as the central game-theoretic solution concept, many important games contain several Nash equilibria and we must determine how to select between them in order to create real strategic agents. Several Nash equilibrium refinement concepts have been proposed and studied for sequential imperfect-information games, the most prominent being trembling-hand perfect equilibrium, quasi-perfect equilibrium, and recently one-sided quasi-perfect equilibrium. These concepts are robust to certain arbitrarily small mistakes, and are guaranteed to always exist; however, we argue that neither of these is the correct concept for developing strong agents in sequential games of imperfect information. We define a new equilibrium refinement concept for extensive-form games called observable perfect equilibrium in which the solution is robust over trembles in publicly-observable action probabilities (not necessarily over all action probabilities that may not be observable by opposing players). Observable perfect equilibrium correctly captures the assumption that the opponent is playing as rationally as possible given mistakes that have been observed (while previous solution concepts do not). We prove that observable perfect equilibrium is always guaranteed to exist, and demonstrate that it leads to a different solution than the prior extensive-form refinements in no-limit poker. We expect observable perfect equilibrium to be a useful equilibrium refinement concept for modeling many important imperfect-information games of interest in artificial intelligence.
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 谷歌翻译
许多真实世界游戏包含可能影响收益,动作空间和信息状态的参数。对于参数的固定值,可以使用标准算法解决游戏。但是,在许多设置中,代理必须采取行动而不知道将提前遇到的参数的值。通常,人类在时间和资源限制的情况下必须做出决定,假设人类可以实时解决游戏是不现实的。我们提出了一个新的框架,使人类决策者能够在没有实时求解器的帮助下做出快速决策。我们展示了适用于各种情况,包括具有多个玩家的设置和不完美信息。
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 谷歌翻译
我们考虑估算人类代理偏好的问题,从战略系统数据反复相互作用。最近,证明了一种称为“量子遗憾”的新估计方法,对人类代理的估计比假设代理是合理的并且达到纳什均衡的经典方法产生更准确的估计;然而,这种方法尚未与考虑人类戏剧行为方面的方法进行比较。在本文中,我们为此目的利用行为经济学的均衡概念,并询问它们与量子后悔和纳什均衡方法相比的操作。我们开发了基于建立的行为均衡模型的四种估计方法,从观察到的正常形式游戏数据中推断人类的公用事业。我们研究的均衡模型是量子响应平衡,动作采样平衡,回报采样平衡和脉冲平衡平衡。我们表明,在这些概念中的一些概念中,推断通过封闭式公式进行分析地实现,而在其他方面则在其他方面只能算法算法。我们使用2x2游戏的实验数据来评估这些行为均衡方法的估计成功。结果表明,它们产生的估计比纳什均衡的估计更准确。与量子后悔方法的比较表明,行为方法具有更好的击中率,但模量遗憾的方法在整体平均平均误差方面表现更好,我们讨论了方法之间的差异。
translated by 谷歌翻译
尽管自1970年代以来就已经知道,普通付款游戏中的全球最佳策略概况是纳什均衡,但全球最优性是严格的要求,它限制了结果的适用性。在这项工作中,我们表明任何本地最佳的对称策略概况也是(全局)NASH平衡。此外,我们证明了这一结果对通用收益和本地最佳的扰动是可靠的。应用于机器学习,我们的结果为任何梯度方法提供了全球保证,该方法在对称策略空间中找到了局部最佳。尽管该结果表明单方面偏差的稳定性,但我们仍然确定了广泛的游戏类别,这些游戏混合了当地的最佳选择,在不对称的偏差下是不稳定的。我们通过在一系列对称游戏中运行学习算法来分析不稳定性的普遍性,并通过讨论结果对多代理RL,合作逆RL和分散的POMDP的适用性来得出结论。
translated by 谷歌翻译
我们考虑战略设置,其中几个用户在重复的在线互动中聘用,辅助最小化的代理商代表他们反复发挥“游戏”。我们研究了代理人的重复游戏的动态和平均结果,并将其视为诱导用户之间的元游戏。我们的主要焦点是用户可以在此元游戏中从“操纵”他们自己的代理商中可以受益于他们自己的代理商。我们正式定义了普通游戏的这种“用户代理元荟萃游戏”模型,讨论了自动化代理动态的不同概念下的属性,并分析了2x2游戏中用户的均衡,其中动态收敛到a单均衡。
translated by 谷歌翻译
\ emph {ex ante}相关性正在成为\ emph {顺序对抗团队游戏}的主流方法,其中一组球员在零和游戏中面对另一支球队。众所周知,团队成员的不对称信息同时使平衡计算\ textsf {apx} - hard和团队的策略在游戏树上不可直接表示。后一个问题阻止采用成功的2个玩家零和游戏的成功工具,例如,\ emph {e.g。},抽象,无regret学习和子游戏求解。这项工作表明,我们可以通过弥合顺序对抗团队游戏和2次玩家游戏之间的差距来恢复这种弱点。特别是,我们提出了一种新的,合适的游戏表示形式,我们称之为\ emph {Team-Public-information},其中团队被代表为单个协调员,他只知道整个团队的共同信息,并向每个成员开出一个行动对于任何可能的私人状态。最终的表示形式是高度\ emph {可解释},是一棵2播放器树,在设计抽象时,团队的策略具有直接解释和更具表现力的行为,并且具有更高的表现力。此外,我们证明了代表性的回报等效性,并提供了直接从广泛形式开始的技术,从而在没有信息损失的情况下产生了更紧凑的表示形式。最后,我们在应用于标准测试床上的技术时对技术进行了实验评估,并将它们的性能与当前的最新状态进行了比较。
translated by 谷歌翻译
游戏历史悠久的历史悠久地作为人工智能进步的基准。最近,使用搜索和学习的方法在一系列完美的信息游戏中表现出强烈的表现,并且使用游戏理论推理和学习的方法对特定的不完美信息扑克变体表示了很强的性能。我们介绍游戏玩家,一个通用算法,统一以前的方法,结合导游搜索,自助学习和游戏理论推理。游戏播放器是实现大型完美和不完美信息游戏中强大实证性能的第一个算法 - 这是一项真正的任意环境算法的重要一步。我们证明了游戏玩家是声音,融合到完美的游戏,因为可用的计算时间和近似容量增加。游戏播放器在国际象棋上达到了强大的表现,然后击败了最强大的公开可用的代理商,在头上没有限制德克萨斯州扑克(Slumbot),击败了苏格兰院子的最先进的代理人,这是一个不完美的信息游戏,说明了引导搜索,学习和游戏理论推理的价值。
translated by 谷歌翻译
在本说明中,我研究了制度和游戏理论假设,这些假设将阻止AI*表示的“超人级”弧形通用智能的出现。这些假设是(i)“心灵自由”,(ii)开源“访问” AI*,以及(iii)与AI*竞争的代表人类代理人的合理性。我证明,在这三个假设下,AI*不可能存在。该结果引起了公共政策的两个即时建议。首先,“克隆”以数字方式受到严格调节,并应禁止假设的脑部进入大脑。其次,如果不公开,应广泛进行AI*研究。
translated by 谷歌翻译
钢筋学习(RL)最近在许多人工智能应用中取得了巨大成功。 RL的许多最前沿应用涉及多个代理,例如,下棋和去游戏,自主驾驶和机器人。不幸的是,古典RL构建的框架不适合多代理学习,因为它假设代理的环境是静止的,并且没有考虑到其他代理的适应性。在本文中,我们介绍了动态环境中的多代理学习的随机游戏模型。我们专注于随机游戏的简单和独立学习动态的发展:每个代理商都是近视,并为其他代理商的战略选择最佳响应类型的行动,而不与对手进行任何协调。为随机游戏开发收敛最佳响应类型独立学习动态有限的进展。我们展示了我们最近提出的简单和独立的学习动态,可保证零汇率随机游戏的融合,以及对此设置中的动态多代理学习的其他同时算法的审查。一路上,我们还重新审视了博弈论和RL文学的一些古典结果,以适应我们独立的学习动态的概念贡献,以及我们分析的数学诺克特。我们希望这篇审查文件成为在博弈论中研究独立和自然学习动态的重新训练的推动力,对于具有动态环境的更具挑战性的环境。
translated by 谷歌翻译
当今许多大型系统的设计,从交通路由环境到智能电网,都依赖游戏理论平衡概念。但是,随着$ n $玩家游戏的大小通常会随着$ n $而成倍增长,标准游戏理论分析实际上是不可行的。最近的方法通过考虑平均场游戏,匿名$ n $玩家游戏的近似值,在这种限制中,玩家的数量是无限的,而人口的状态分布,而不是每个单独的球员的状态,是兴趣。然而,迄今为止研究最多的平均场平衡的平均场nash平衡的实际可计算性通常取决于有益的非一般结构特性,例如单调性或收缩性能,这是已知的算法收敛所必需的。在这项工作中,我们通过开发均值相关和与粗相关的平衡的概念来研究平均场比赛的替代途径。我们证明,可以使用三种经典算法在\ emph {ash All Games}中有效地学习它们,而无需对游戏结构进行任何其他假设。此外,我们在文献中已经建立了对应关系,从而获得了平均场 - $ n $玩家过渡的最佳范围,并经验证明了这些算法在简单游戏中的收敛性。
translated by 谷歌翻译
我们分析了一种方案,其中软件代理作为后悔最小化算法代表他们的用户参与重复拍卖。我们研究了第一个价格和第二次价格拍卖,以及他们的广义版本(例如,作为用于广告拍卖的版本)。利用理论分析和模拟,我们展示了,令人惊讶的是,在二次价格拍卖中,球员的激励措施将他们的真正估值释放到自己的学习代理,而在第一次价格拍卖中,这是所有球员如实的主要战略向他们的代理商报告他们的估值。
translated by 谷歌翻译
在最近在两人,零和游戏中取得成功的驱动下,人工智能在游戏中的工作越来越重视产生基于平衡策略的算法。但是,这种方法在培养通用游戏或两个以上玩家的能力的玩家中的效果较小,而不是在两人游戏中的零和零游戏中。一个有吸引力的替代方法是考虑自适应算法,以确保相对于修改行为可以实现的方面的强劲表现。这种方法还导致了游戏理论分析,但是在关节学习动力学而不是均衡的代理行为引起的相关性游戏中。我们在一般的顺序决策环境中发展并倡导这一对学习的事后理性理性框架。为此,我们在广泛的游戏中重新检查了介导的平衡和偏差类型,从而获得了更完整的理解和解决过去的误解。我们提出了一组示例,说明了文献中每种平衡的独特优势和劣势,并证明没有可牵引的概念可以包含所有其他概念。这一探究线在与反事实遗憾最小化(CFR)家族中算法相对应的偏差和平衡类的定义中达到顶点,将它们与文献中的所有其他人联系起来。更详细地研究CFR进一步导致相关游戏中合理性的新递归定义,该定义以自然适用于后代评估的方式扩展了顺序合理性。
translated by 谷歌翻译
主导的行动是自然的(也许是最简单的)多代理概括的子最优动作,如标准单代理决策中的那样。因此类似于标准强盗学习,多代理系统中的基本学习问题是如果他们只能观察到他们播放动作的回报的嘈杂的强盗反馈,那么代理商可以学会有效地消除所有主导的动作。令人惊讶的是,尽管有一个看似简单的任务,我们展示了一个相当负面的结果;也就是说,标准没有遗憾的算法 - 包括整个双平均算法的家庭 - 可呈指数级地取消逐渐消除所有主导的行动。此外,具有较强的交换后悔的算法也遭受了类似的指数低效率。为了克服这些障碍,我们开发了一种新的算法,调整EXP3,历史奖励减少(exp3-DH); Exp3-DH逐渐忘记仔细量身定制的速率。我们证明,当所有代理运行Exp3-DH(A.K.A.,在多代理学习中自行发行)时,所有主导的行动都可以在多项多轮内迭代地消除。我们的实验结果进一步证明了Exp3-DH的效率,即使是那些专门用于在游戏中学习的最先进的强盗算法,也无法有效地消除所有主导的行动。
translated by 谷歌翻译
游戏理论到目前为止在各个领域都发现了许多应用,包括经济学,工业,法学和人工智能,每个玩家都只关心自己对非合作或合作方式的兴趣,但对其他玩家没有明显的恶意。但是,在许多实际应用中,例如扑克,国际象棋,逃避者追求,毒品拦截,海岸警卫队,网络安全和国防,球员通常都具有对抗性立场,也就是说,每个球员的自私行动不可避免地或故意造成损失或对其他球员造成严重破坏。沿着这条线,本文对在对抗性游戏中广泛使用的三种主要游戏模型(即零和零正常形式和广泛形式游戏,stackelberg(Security)游戏,零和差异游戏)提供了系统的调查。观点,包括游戏模型的基本知识,(近似)平衡概念,问题分类,研究前沿,(近似)最佳策略寻求技术,普遍的算法和实际应用。最后,还讨论了有关对抗性游戏的有希望的未来研究方向。
translated by 谷歌翻译
We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. Such game access is common in reinforcement learning settings, where the environment is typically treated as a black box. To tackle this problem, we apply zeroth-order optimization techniques that combine smoothed gradient estimators with equilibrium-finding dynamics. We model players' strategies using artificial neural networks. In particular, we use randomized policy networks to model mixed strategies. These take noise in addition to an observation as input and can flexibly represent arbitrary observation-dependent, continuous-action distributions. Being able to model such mixed strategies is crucial for tackling continuous-action games that lack pure-strategy equilibria. We evaluate the performance of our method using an approximation of the Nash convergence metric from game theory, which measures how much players can benefit from unilaterally changing their strategy. We apply our method to continuous Colonel Blotto games, single-item and multi-item auctions, and a visibility game. The experiments show that our method can quickly find high-quality approximate equilibria. Furthermore, they show that the dimensionality of the input noise is crucial for performance. To our knowledge, this paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
translated by 谷歌翻译
经济学和政策等现实世界应用程序往往涉及解决多智能运动游戏与两个独特的特点:(1)代理人本质上是不对称的,并分成领导和追随者; (2)代理商有不同的奖励功能,因此游戏是普通的。该领域的大多数现有结果侧重于对称解决方案概念(例如纳什均衡)或零和游戏。它仍然开放了如何学习Stackelberg均衡 - 从嘈杂的样本有效地纳入均衡的不对称模拟 - 纳入均衡。本文启动了对Birtit反馈设置中Stackelberg均衡的样本高效学习的理论研究,我们只观察奖励的噪音。我们考虑三个代表双人普通和游戏:强盗游戏,强盗加固学习(Bandit-RL)游戏和线性匪徒游戏。在所有这些游戏中,我们使用有义的许多噪声样本来确定Stackelberg均衡和其估计版本的确切值之间的基本差距,无论算法如何,都无法封闭信息。然后,我们在对上面识别的差距最佳的基础上的数据高效学习的样本高效学习的敏锐积极结果,在依赖于依赖性的差距,误差容限和动作空间的大小,匹配下限。总体而言,我们的结果在嘈杂的强盗反馈下学习Stackelberg均衡的独特挑战,我们希望能够在未来的研究中阐明这一主题。
translated by 谷歌翻译