在博弈论中的精髓结果是von Neumann的Minmax定理，这些定理使得零和游戏承认基本上独特的均衡解决方案。古典学习结果对本定理构建，以表明在线无后悔动态会聚到零和游戏中的时间平均意义上的均衡。在过去几年中，一个关键的研究方向专注于表征这种动态的日常行为。一般结果在这个方向上表明，广泛的在线学习动态是循环的，并且在零和游戏中正式的Poincar {e}复发。在具有时间不变均衡的定期零和游戏的情况下，我们分析了这些在线学习行为的稳健性。该模型概括了通常的重复游戏制定，同时也是参与者之间反复竞争的现实和自然模型，这取决于外源性环境变化，如日期效果，周到一周的趋势和季节性。有趣的是，即使在最简单的这种情况下，也可能失败的时间平均收敛性，尽管有均衡是固定的。相比之下，使用新颖的分析方法，我们表明Poincar \'{E}尽管这些动态系统的复杂性，非自主性质，但是普及的复发概括。
translated by 谷歌翻译
我们考虑战略设置，其中几个用户在重复的在线互动中聘用，辅助最小化的代理商代表他们反复发挥“游戏”。我们研究了代理人的重复游戏的动态和平均结果，并将其视为诱导用户之间的元游戏。我们的主要焦点是用户可以在此元游戏中从“操纵”他们自己的代理商中可以受益于他们自己的代理商。我们正式定义了普通游戏的这种“用户代理元荟萃游戏”模型，讨论了自动化代理动态的不同概念下的属性，并分析了2x2游戏中用户的均衡，其中动态收敛到a单均衡。
translated by 谷歌翻译
迄今为止，游戏中的学习研究主要集中在正常形式游戏上。相比之下，我们以广泛的形式游戏（EFG），尤其是在许多代理商远远落后的EFG中对学习的理解，尽管它们与许多现实世界的应用更加接近。我们考虑了网络零和广泛表单游戏的天然类别，该游戏结合了代理收益的全球零和属性，图形游戏的有效表示以及EFG的表达能力。我们检查了这些游戏中乐观梯度上升（OGA）的收敛属性。我们证明，这种在线学习动力学的时间平均值表现出$ O（1/t）$ rate contergence convergence contergence contergence。此外，我们表明，对于某些与游戏有关的常数$ c> 0 $，日常行为也与速率$ o（c^{ - t}）$收敛到nash。
translated by 谷歌翻译
We propose a multi-agent reinforcement learning dynamics, and analyze its convergence properties in infinite-horizon discounted Markov potential games. We focus on the independent and decentralized setting, where players can only observe the realized state and their own reward in every stage. Players do not have knowledge of the game model, and cannot coordinate with each other. In each stage of our learning dynamics, players update their estimate of a perturbed Q-function that evaluates their total contingent payoff based on the realized one-stage reward in an asynchronous manner. Then, players independently update their policies by incorporating a smoothed optimal one-stage deviation strategy based on the estimated Q-function. A key feature of the learning dynamics is that the Q-function estimates are updated at a faster timescale than the policies. We prove that the policies induced by our learning dynamics converge to a stationary Nash equilibrium in Markov potential games with probability 1. Our results demonstrate that agents can reach a stationary Nash equilibrium in Markov potential games through simple learning dynamics under the minimum information environment.
translated by 谷歌翻译
我们的工作侧重于额外的渐变学习算法，用于在双线性零和游戏中查找纳什均衡。该方法可以正式被认为是乐观镜下降\ Cite {DBLP：Cenf / ICLR / Mertikopouloslz19}的典型方法，用于中间梯度步骤，基本上导致计算（近似）最佳反应策略先前迭代的轮廓。虽然乍一看，由于不合理的大，但是对于迭代算法，中间学习步骤，我们证明该方法保证了持续收敛到均衡。特别是，我们表明该算法首先达到$ \ eta ^ {1 / rho} $ - 近似纳什均衡，以$ \ rho> 1 $，通过减少每次迭代的kullback-leibler分歧至少$ \ omega （\ eta ^ {1+ \ frac {1} {\ rho}）$，因为足够小的学习率，$ \ eta $直到该方法成为承包地图，并收敛到确切的均衡。此外，我们对乘法权重更新方法的乐观变体进行实验比较，\ Cite {Daskalakis2019LastITERATECZ}并显示我们的算法具有显着的实际潜力，因为它在加速收敛方面提供了大量的收益。
translated by 谷歌翻译
我们开发了一个统一的随机近似框架，用于分析游戏中多学院在线学习的长期行为。我们的框架基于“原始偶尔”，镜像的Robbins-Monro（MRM）模板，该模板涵盖了各种各样的流行游戏理论学习算法（梯度方法，乐观的变体，Exp3算法，用于基于付费的反馈，在有限游戏等中）。除了提供这些算法的综合视图外，提出的MRM蓝图还使我们能够在连续和有限的游戏中获得渐近和有限时间的广泛新收敛结果。
translated by 谷歌翻译
我们在无限地平线上享受多智能经纪增强学习（Marl）零汇率马尔可夫游戏。我们专注于分散的Marl的实用性但具有挑战性的环境，其中代理人在没有集中式控制员的情况下做出决定，但仅根据自己的收益和当地行动进行了协调。代理商不需要观察对手的行为或收益，可能甚至不忘记对手的存在，也不得意识到基础游戏的零金额结构，该环境也称为学习文学中的彻底解散游戏。在本文中，我们开发了一种彻底的解耦Q学习动态，既合理和收敛则：当对手遵循渐近静止战略时，学习动态会收敛于对对手战略的最佳反应;当两个代理采用学习动态时，它们会收敛到游戏的纳什均衡。这种分散的环境中的关键挑战是从代理商的角度来看环境的非公平性，因为她自己的回报和系统演变都取决于其他代理人的行为，每个代理商同时和独立地互补她的政策。要解决此问题，我们开发了两个时间尺度的学习动态，每个代理会更新她的本地Q函数和value函数估计，后者在较慢的时间内发生。
translated by 谷歌翻译
当今许多大型系统的设计，从交通路由环境到智能电网，都依赖游戏理论平衡概念。但是，随着$ n $玩家游戏的大小通常会随着$ n $而成倍增长，标准游戏理论分析实际上是不可行的。最近的方法通过考虑平均场游戏，匿名$ n $玩家游戏的近似值，在这种限制中，玩家的数量是无限的，而人口的状态分布，而不是每个单独的球员的状态，是兴趣。然而，迄今为止研究最多的平均场平衡的平均场nash平衡的实际可计算性通常取决于有益的非一般结构特性，例如单调性或收缩性能，这是已知的算法收敛所必需的。在这项工作中，我们通过开发均值相关和与粗相关的平衡的概念来研究平均场比赛的替代途径。我们证明，可以使用三种经典算法在\ emph {ash All Games}中有效地学习它们，而无需对游戏结构进行任何其他假设。此外，我们在文献中已经建立了对应关系，从而获得了平均场 - $ n $玩家过渡的最佳范围，并经验证明了这些算法在简单游戏中的收敛性。
translated by 谷歌翻译
我们展示了一种新颖的虚构播放动态变种，将经典虚拟游戏与Q学习进行随机游戏，分析其在双球零点随机游戏中的收敛性。我们的动态涉及在对手战略上形成信仰的球员以及他们自己的延续支付（Q-Function），并通过使用估计的延续收益来扮演贪婪的最佳回应。玩家从对对手行动的观察开始更新他们的信仰。学习动态的一个关键属性是，更新Q函数的信念发生在较慢的时间上，而不是对策略的信念的更新。我们在基于模型和无模式的情况下（不了解播放器支付功能和国家过渡概率），对策略的信念会聚到零和随机游戏的固定混合纳什均衡。
translated by 谷歌翻译
钢筋学习（RL）最近在许多人工智能应用中取得了巨大成功。 RL的许多最前沿应用涉及多个代理，例如，下棋和去游戏，自主驾驶和机器人。不幸的是，古典RL构建的框架不适合多代理学习，因为它假设代理的环境是静止的，并且没有考虑到其他代理的适应性。在本文中，我们介绍了动态环境中的多代理学习的随机游戏模型。我们专注于随机游戏的简单和独立学习动态的发展：每个代理商都是近视，并为其他代理商的战略选择最佳响应类型的行动，而不与对手进行任何协调。为随机游戏开发收敛最佳响应类型独立学习动态有限的进展。我们展示了我们最近提出的简单和独立的学习动态，可保证零汇率随机游戏的融合，以及对此设置中的动态多代理学习的其他同时算法的审查。一路上，我们还重新审视了博弈论和RL文学的一些古典结果，以适应我们独立的学习动态的概念贡献，以及我们分析的数学诺克特。我们希望这篇审查文件成为在博弈论中研究独立和自然学习动态的重新训练的推动力，对于具有动态环境的更具挑战性的环境。
translated by 谷歌翻译
游戏中的学习理论在AI社区中很突出，这是由多个不断上升的应用程序（例如多代理增强学习和生成对抗性网络）的动机。我们提出了突变驱动的乘法更新（M2WU），以在两人零和零正常形式游戏中学习平衡，并证明它在全面和嘈杂的信息反馈设置中都表现出了最后的题融合属性。在全信息反馈设置中，玩家观察了实用程序功能的确切梯度向量。另一方面，在嘈杂的信息反馈设置中，他们只能观察到嘈杂的梯度向量。现有的算法，包括众所周知的乘法权重更新（MWU）和乐观的MWU（OMWU）算法，未能收敛到具有嘈杂的信息反馈的NASH平衡。相反，在两个反馈设置中，M2WU表现出最后的近期收敛到NASH平衡附近的固定点。然后，我们证明它通过迭代地适应突变项来收敛到精确的NASH平衡。我们从经验上确认，M2WU在可剥削性和收敛速率方面胜过MWU和OMWU。
translated by 谷歌翻译
在这项研究中，我们考虑了两个玩家零和游戏中的正规领导者（FTRL）动力学的变体。在时间平衡策略时，FTRL保证会融合到NASH平衡，而许多变体都遭受了极限自行车行为的问题，即缺乏最后的介质收敛保证。为此，我们提出了一种突变FTRL（M-FTRL），该算法引入了用于动作概率扰动的突变。然后，我们研究了M-FTRL的连续时间动力学，并提供了强大的收敛保证，可以向固定点提供近似于NASH平衡的固定点。此外，我们的仿真表明，M-FTRL比FTRL和乐观的FTRL在全信息反馈下享有更快的收敛速度，并且在强盗反馈下表现出明显的收敛性。
translated by 谷歌翻译
经验和实验证据表明，人工智能算法学会收取超竞争价格。在本文中，我们开发了一种理论模型来通过自适应学习算法研究勾结。使用流体近似技术，我们表征了一般游戏的连续时间学习成果，并确定勾结的主要驱动力：协调偏见。在一个简单的主导策略游戏中，我们展示了算法估计之间的相关性如何导致持续的偏见，从长远来看持续犯罪行动。我们证明，使用反事实收益来告知其更新的算法避免了这种偏见并融合了主导策略。我们设计了一种带有反馈的机制：设计师揭示了事前信息以帮助反事实计算。我们表明，这种机制实现了社会最佳。最后，我们将我们的框架应用于文献中研究和拍卖的两个模拟，并分析结果合理化。
translated by 谷歌翻译
我们分析了一种方案，其中软件代理作为后悔最小化算法代表他们的用户参与重复拍卖。我们研究了第一个价格和第二次价格拍卖，以及他们的广义版本（例如，作为用于广告拍卖的版本）。利用理论分析和模拟，我们展示了，令人惊讶的是，在二次价格拍卖中，球员的激励措施将他们的真正估值释放到自己的学习代理，而在第一次价格拍卖中，这是所有球员如实的主要战略向他们的代理商报告他们的估值。
translated by 谷歌翻译
在本文中，我们提出了连续时间游戏理论镜中下降（MD）动态的二阶扩展，称为MD2，其收敛于MED（但不一定是严格的）变分性稳定状态（VSS）而不使用常见辅助技术，如平均或折扣。我们表明MD2在轻微修改后享有无悔的趋势以及对强大的VSS的指数汇率。此外，MD2可用于导出许多新颖的原始空间动态。最后，使用随机近似技术，我们提供了对内部仅噪声的离散时间MD2的收敛保证。提供了所选模拟以说明我们的结果。
translated by 谷歌翻译
在拍卖领域，了解重复拍卖中学习动态的收敛属性是一个及时，重要的问题，例如在线广告市场中有许多应用程序。这项工作着重于重复的首次价格拍卖，该物品具有固定值的竞标者学会使用基于平均值的算法出价 - 大量的在线学习算法，其中包括流行的无regret算法，例如多重权重更新，并遵循扰动的领导者。我们完全表征了基于均值算法的学习动力学，从收敛到拍卖的NASH平衡方面，具有两种感觉：（1）时间平均水平：竞标者在bidiper the NASH平衡方面的回合分数，在极限中均在极限中。 ; （2）最后一题：竞标者的混合策略概况接近限制的NASH平衡。具体而言，结果取决于最高值的投标人的数量： - 如果数量至少为三个，则竞标动力学几乎可以肯定地收敛到拍卖的NASH平衡，无论是在时间平时还是在最后近期的情况下。 - 如果数字为两个，则竞标动力学几乎可以肯定会在时间平时收敛到NASH平衡，但不一定在最后近期。 - 如果数字是一个，则竞标动力学可能不会在时间平均值或最后近期的时间内收敛到NASH平衡。我们的发现为学习算法的融合动力学研究开辟了新的可能性。
translated by 谷歌翻译
最近的多人游戏的理论和应用方面的最新进步，从电子运动到多种子体生成的对抗网络，我们专注于团队零和游戏中的最大优化。在这类游戏中，玩家分为两支队伍，在同一支队内等等，对手团队的相反标志。与TextBook二手零和游戏不同，在我们的类中找到纳什均衡可以被证明是CLS-Hard，即，它不太可能具有用于计算NASH均衡的多项式时间算法。此外，在该广义框架中，使用梯度下降上升（GDA），其乐观变体和额外梯度，我们建立了即使是渐近的最后一次迭代或时间平均收敛到纳什均衡。具体来说，我们展示了一个诱导效用是\ emph {non}的团队游戏系列\ \ emph {non}有吸引力的\ {per-se}混合的纳什均衡，作为底层优化景观的严格鞍点。利用控制理论的技术，我们通过设计局部收敛的修改GDA来补充这些负面结果，以纳入均衡。最后，我们讨论了我们的框架与AI架构的联系，其中与多助理生成对冲网络这样的团队竞争结构。
translated by 谷歌翻译
在本文中，我们研究了具有约束策略空间的两人双线零和游戏。这种约束的自然发生的一个实例是使用混合策略，这与概率单纯限制相对应。我们提出和分析交替的镜面下降算法，其中每个玩家都会轮流采取镜子下降算法采取行动，以进行约束优化。我们将交替的镜像下降解释为双重空间中偏斜梯度流的交替离散化，并使用凸优化和修改能量功能的工具来建立$ O（k^{ - 2/3}）$绑定其平均后悔$ k $迭代。与同时版本的镜子下降算法相比，这可以定量验证该算法的更好行为，该算法的同时版本可以发散并产生$ O（k^{ - 1/2}）$平均遗憾。在不受约束的特殊情况下，我们的结果恢复了在（Bailey等人，Colt 2020）中研究的零和零游戏的交替梯度下降算法的行为。
translated by 谷歌翻译
最近，Daskalakis，Fisselson和Golowich（DFG）（Neurips`21）表明，如果所有代理在多人普通和正常形式游戏中采用乐观的乘法权重更新（OMWU），每个玩家的外部遗憾是$ o（\ textrm {polylog}（t））$ the游戏的$重复。我们从外部遗憾扩展到内部遗憾并交换后悔，从而建立了以$ \ tilde {o}的速率收敛到近似相关均衡的近似相关均衡（t ^ { - 1}）$。由于陈和彭（神经潜行群岛20），这实质上提高了以陈和彭（NEURIPS20）的相关均衡的相关均衡率，并且在无遗憾的框架内是最佳的 - 以$ $ $ to to polylogarithmic因素。为了获得这些结果，我们开发了用于建立涉及固定点操作的学习动态的高阶平滑的新技术。具体而言，我们确定STOLTZ和LUGOSI（Mach Learn`05）的无内部遗憾学习动态在组合空间上的无外部后悔动态等效地模拟。这使我们可以在指数大小的集合上交易多项式大型马尔可夫链的计算，用于在指数大小的集合上的（更良好的良好）的线性变换，使我们能够利用类似的技术作为DGF到接近最佳地结合内心遗憾。此外，我们建立了$ O（\ textrm {polylog}（t））$ no-swap-recreet遗憾的blum和mansour（bm）的经典算法（JMLR`07）。我们这样做是通过基于Cauchy积分的技术来介绍DFG的更有限的组合争论。除了对BM的近乎最优遗憾保证的阐明外，我们的论点还提供了进入各种方式的洞察，其中可以在分析更多涉及的学习算法中延长和利用DFG的技术。
translated by 谷歌翻译
我们研究了马尔可夫潜在游戏（MPG）中多机构增强学习（RL）问题的策略梯度方法的全球非反应收敛属性。要学习MPG的NASH平衡，在该MPG中，状态空间的大小和/或玩家数量可能非常大，我们建议使用TANDEM所有玩家运行的新的独立政策梯度算法。当梯度评估中没有不确定性时，我们表明我们的算法找到了$ \ epsilon $ -NASH平衡，$ o（1/\ epsilon^2）$迭代复杂性并不明确取决于状态空间大小。如果没有确切的梯度，我们建立$ O（1/\ epsilon^5）$样品复杂度在潜在的无限大型状态空间中，用于利用函数近似的基于样本的算法。此外，我们确定了一类独立的政策梯度算法，这些算法都可以融合零和马尔可夫游戏和马尔可夫合作游戏，并与玩家不喜欢玩的游戏类型。最后，我们提供了计算实验来证实理论发展的优点和有效性。
translated by 谷歌翻译