Cheung和Piliouras（2020）最近表明，乘法权重更新方法的两个变体 - OMWU和MWU-显示的相反的收敛性属性取决于游戏是零和合作的。受这项工作的启发以及有关学习以优化单个功能的最新文献，我们引入了一个新的框架，用于学习在游戏中与NASH Eqeilibria的最后近期融合，在这种情况下，更新规则的系数（学习率）沿着轨迹学习了，这是由增强力学学习的以游戏性质为条件的学习策略：\ textit {游戏签名}。我们使用两人游戏的新分解构建后者，分成对应于交换性投影操作员的八个组件，从而概括和统一文献中研究的最新游戏概念。当学习系数时，我们比较了各种更新规则的性能，并表明RL策略能够利用各种游戏类型的游戏签名。在此过程中，我们介绍了CMWU，这是一种将共识优化扩展到受约束案例的新算法，对零和bimatrix游戏具有本地收敛保证，并证明它在具有恒定系数和跨系数的零和零游戏上都具有竞争性能学习系数时的频谱。

我们的工作侧重于额外的渐变学习算法，用于在双线性零和游戏中查找纳什均衡。该方法可以正式被认为是乐观镜下降\ Cite {DBLP：Cenf / ICLR / Mertikopouloslz19}的典型方法，用于中间梯度步骤，基本上导致计算（近似）最佳反应策略先前迭代的轮廓。虽然乍一看，由于不合理的大，但是对于迭代算法，中间学习步骤，我们证明该方法保证了持续收敛到均衡。特别是，我们表明该算法首先达到$ \ eta ^ {1 / rho} $ - 近似纳什均衡，以$ \ rho> 1 $，通过减少每次迭代的kullback-leibler分歧至少$ \ omega （\ eta ^ {1+ \ frac {1} {\ rho}）$，因为足够小的学习率，$ \ eta $直到该方法成为承包地图，并收敛到确切的均衡。此外，我们对乘法权重更新方法的乐观变体进行实验比较，\ Cite {Daskalakis2019LastITERATECZ}并显示我们的算法具有显着的实际潜力，因为它在加速收敛方面提供了大量的收益。

最近的多人游戏的理论和应用方面的最新进步，从电子运动到多种子体生成的对抗网络，我们专注于团队零和游戏中的最大优化。在这类游戏中，玩家分为两支队伍，在同一支队内等等，对手团队的相反标志。与TextBook二手零和游戏不同，在我们的类中找到纳什均衡可以被证明是CLS-Hard，即，它不太可能具有用于计算NASH均衡的多项式时间算法。此外，在该广义框架中，使用梯度下降上升（GDA），其乐观变体和额外梯度，我们建立了即使是渐近的最后一次迭代或时间平均收敛到纳什均衡。具体来说，我们展示了一个诱导效用是\ emph {non}的团队游戏系列\ \ emph {non}有吸引力的\ {per-se}混合的纳什均衡，作为底层优化景观的严格鞍点。利用控制理论的技术，我们通过设计局部收敛的修改GDA来补充这些负面结果，以纳入均衡。最后，我们讨论了我们的框架与AI架构的联系，其中与多助理生成对冲网络这样的团队竞争结构。

我们开发了一个统一的随机近似框架，用于分析游戏中多学院在线学习的长期行为。我们的框架基于“原始偶尔”，镜像的Robbins-Monro（MRM）模板，该模板涵盖了各种各样的流行游戏理论学习算法（梯度方法，乐观的变体，Exp3算法，用于基于付费的反馈，在有限游戏等中）。除了提供这些算法的综合视图外，提出的MRM蓝图还使我们能够在连续和有限的游戏中获得渐近和有限时间的广泛新收敛结果。

在本文中，我们提出了连续时间游戏理论镜中下降（MD）动态的二阶扩展，称为MD2，其收敛于MED（但不一定是严格的）变分性稳定状态（VSS）而不使用常见辅助技术，如平均或折扣。我们表明MD2在轻微修改后享有无悔的趋势以及对强大的VSS的指数汇率。此外，MD2可用于导出许多新颖的原始空间动态。最后，使用随机近似技术，我们提供了对内部仅噪声的离散时间MD2的收敛保证。提供了所选模拟以说明我们的结果。

在本文中，我们调查了正规化的力量，即在解决广泛形式的游戏（EFGS）方面的加强学习和优化方面的常见技术。我们提出了一系列新算法，基于正规化游戏的回报功能，并建立一组收敛结果，这些结果严格改善了现有的假设或更强的收敛保证。特别是，我们首先证明了膨胀的乐观镜下降（DOMD），一种用于求解EFG的有效变体，具有自适应正则化可以实现快速的$ \ tilde o（1/t）$ last-Ilt-Ilt-Ilt-It-last-Ilt-It-titer-In-titer-Inter-In-Elt-It-Triperate Connergengengenge没有纳什平衡（NE）的独特性假设。此外，正规化的膨胀倍增权重更新（reg-domwu）是reg-domd的实例，进一步享受了$ \ tilde o（1/t）$ ther-tir-tir-tir-tir-tir-tir-ter-tir-tir-ter-tir-tir-tir-tir-tir-tir-tir-tir-tir-ter-ter-ter-ter-ter-ter-ter-ter-ter-tir-ter-ter-tir-trientate Convergence。这解决了一个关于OMWU算法是否可以在没有EFG和正常形式游戏文献中的唯一假设的情况下获得的迭代融合的一个悬而未决的问题。其次，我们表明，正式化的反事实遗憾最小化（reg-cfr），具有乐观的镜像下降算法的变体作为遗憾少量器，可以实现$ o（1/t^{1/4}）$ best-Ilterate和$ $ o（1/t^{3/4}）$用于在EFG中查找NE的平均值收敛率。最后，我们表明Reg-CFR可以实现渐近的最后一介质收敛，而最佳$ O（1/t）$平均识别收敛速率可用于查找扰动的EFGS的NE，这对于找到近似广泛形式的完美非常有用平衡（EFPE）。据我们所知，它们构成了CFR型算法的第一个最后近期收敛结果，同时匹配SOTA平均识别收敛速率在寻找非扰动的EFG中的NE中。我们还提供数值结果来证实我们算法的优势。

我们研究了马尔可夫潜在游戏（MPG）中多机构增强学习（RL）问题的策略梯度方法的全球非反应收敛属性。要学习MPG的NASH平衡，在该MPG中，状态空间的大小和/或玩家数量可能非常大，我们建议使用TANDEM所有玩家运行的新的独立政策梯度算法。当梯度评估中没有不确定性时，我们表明我们的算法找到了$ \ epsilon $ -NASH平衡，$ o（1/\ epsilon^2）$迭代复杂性并不明确取决于状态空间大小。如果没有确切的梯度，我们建立$ O（1/\ epsilon^5）$样品复杂度在潜在的无限大型状态空间中，用于利用函数近似的基于样本的算法。此外，我们确定了一类独立的政策梯度算法，这些算法都可以融合零和马尔可夫游戏和马尔可夫合作游戏，并与玩家不喜欢玩的游戏类型。最后，我们提供了计算实验来证实理论发展的优点和有效性。

当今许多大型系统的设计，从交通路由环境到智能电网，都依赖游戏理论平衡概念。但是，随着$ n $玩家游戏的大小通常会随着$ n $而成倍增长，标准游戏理论分析实际上是不可行的。最近的方法通过考虑平均场游戏，匿名$ n $玩家游戏的近似值，在这种限制中，玩家的数量是无限的，而人口的状态分布，而不是每个单独的球员的状态，是兴趣。然而，迄今为止研究最多的平均场平衡的平均场nash平衡的实际可计算性通常取决于有益的非一般结构特性，例如单调性或收缩性能，这是已知的算法收敛所必需的。在这项工作中，我们通过开发均值相关和与粗相关的平衡的概念来研究平均场比赛的替代途径。我们证明，可以使用三种经典算法在\ emph {ash All Games}中有效地学习它们，而无需对游戏结构进行任何其他假设。此外，我们在文献中已经建立了对应关系，从而获得了平均场 - $ n $玩家过渡的最佳范围，并经验证明了这些算法在简单游戏中的收敛性。

本文研究了用于多机构增强学习的政策优化算法。我们首先在全信息设置中提出了针对两人零和零和马尔可夫游戏的算法框架，其中每次迭代均使用一个策略更新，使用某个矩阵游戏算法在每个状态下进行策略更新，并带有一个带有特定的值更新步骤学习率。该框架统一了许多现有和新的政策优化算法。我们表明，只要矩阵游戏算法在每种状态下，该算法的州平均策略会收敛到游戏的近似NASH平衡（NE），只要矩阵游戏算法在每个状态下都具有低称重的遗憾价值更新。接下来，我们证明，该框架与每个状态（和平滑值更新）的乐观跟踪定制领导者（oftrl）算法可以找到$ \ Mathcal {\ widetilde {o}}（t^{ - 5 /6}）$ t $迭代中的$近似NE，并且具有稍微修改的值更新规则的类似算法可实现更快的$ \ Mathcal {\ widetilde {o}}}}（t^{ - 1}）$收敛率。这些改进了当前最佳$ \ Mathcal {\ widetilde {o}}}（t^{ - 1/2}）$对称策略优化类型算法的速率。我们还将此算法扩展到多玩家通用-SUM Markov游戏，并显示$ \ MATHCAL {\ widetilde {o}}}（t^{ - 3/4}）$收敛率与粗相关均衡（CCE）。最后，我们提供了一个数值示例来验证我们的理论并研究平滑价值更新的重要性，并发现使用“渴望”的价值更新（等同于独立的自然策略梯度算法）也可能会大大减慢收敛性，即使在$ h = 2 $层的简单游戏。

尽管自1970年代以来就已经知道，普通付款游戏中的全球最佳策略概况是纳什均衡，但全球最优性是严格的要求，它限制了结果的适用性。在这项工作中，我们表明任何本地最佳的对称策略概况也是（全局）NASH平衡。此外，我们证明了这一结果对通用收益和本地最佳的扰动是可靠的。应用于机器学习，我们的结果为任何梯度方法提供了全球保证，该方法在对称策略空间中找到了局部最佳。尽管该结果表明单方面偏差的稳定性，但我们仍然确定了广泛的游戏类别，这些游戏混合了当地的最佳选择，在不对称的偏差下是不稳定的。我们通过在一系列对称游戏中运行学习算法来分析不稳定性的普遍性，并通过讨论结果对多代理RL，合作逆RL和分散的POMDP的适用性来得出结论。

我们考虑在具有强盗反馈的未知游戏中的在线无遗憾的学习，其中每个代理只在每次都观察到其奖励 - 所有参与者当前的联合行动 - 而不是其渐变。我们专注于平稳且强烈单调的游戏类，并在其中研究最佳的无遗憾。利用自我协调的障碍功能，我们首先构建在线强盗凸优化算法，并表明它实现了平滑且强烈 - 凹陷的支付下$ \ tilde {\ theta}（\ sqrt {t}）$的单代理最佳遗憾职能。然后，如果每个代理在强烈单调的游戏中应用这种无悔的学习算法，则以$ \ tilde {\ theta}的速率，联合动作会收敛于\ texit {last erate}到唯一的纳什均衡（1 / \ sqrt {t}）$。在我们的工作之前，同一类游戏中的最熟悉的融合率是$ O（1 / T ^ {1/3}）$（通过不同的算法实现），从而留下了最佳无悔的问题学习算法（因为已知的下限为$ \ omega（1 / \ sqrt {t}）$）。我们的结果因此通过识别第一双重最佳强盗学习算法来解决这个公开问题并促进强盗游戏 - 理论学习的广泛景观，因为它达到了（达到了日志因子）单王子学习和最佳的最佳遗憾多代理学习中的最后迭代收敛速度。我们还展示了几项模拟研究的结果 - Cournot竞争，凯利拍卖和分布式正则化物流回归 - 以证明我们算法的功效。

用于解决无约束光滑游戏的两个最突出的算法是经典随机梯度下降 - 上升（SGDA）和最近引入的随机共识优化（SCO）[Mescheder等，2017]。已知SGDA可以收敛到特定类别的游戏的静止点，但是当前的收敛分析需要有界方差假设。 SCO用于解决大规模对抗问题，但其收敛保证仅限于其确定性变体。在这项工作中，我们介绍了预期的共同胁迫条件，解释了它的好处，并在这种情况下提供了SGDA和SCO的第一次迭代收敛保证，以解决可能是非单调的一类随机变分不等式问题。我们将两种方法的线性会聚到解决方案的邻域时，当它们使用恒定的步长时，我们提出了富有识别的步骤化切换规则，以保证对确切解决方案的融合。此外，我们的收敛保证在任意抽样范式下担保，因此，我们对迷你匹配的复杂性进行了解。

计算NASH平衡策略是多方面强化学习中的一个核心问题，在理论和实践中都受到广泛关注。但是，到目前为止，可证明的保证金仅限于完全竞争性或合作的场景，或者在大多数实际应用中实现难以满足的强大假设。在这项工作中，我们通过调查Infinite-Horizo​​n \ Emph {对抗性团队Markov Games}，这是一场自然而充分动机的游戏，其中一组相同兴奋的玩家 - 在没有任何明确的情况下，这是一个自然而有动机的游戏，这是一场自然而有动机的游戏，而偏离了先前的结果。协调或交流 - 正在与对抗者竞争。这种设置允许对零和马尔可夫潜在游戏进行统一处理，并作为模拟更现实的战略互动的一步，这些互动具有竞争性和合作利益。我们的主要贡献是第一种计算固定$ \ epsilon $ - Approximate Nash Equilibria在对抗性团队马尔可夫游戏中具有计算复杂性的算法，在游戏的所有自然参数中都是多项式的，以及$ 1/\ epsilon $。拟议的算法特别自然和实用，它基于为团队中的每个球员执行独立的政策梯度步骤，并与对手侧面的最佳反应同时；反过来，通过解决精心构造的线性程序来获得对手的政策。我们的分析利用非标准技术来建立具有非convex约束的非线性程序的KKT最佳条件，从而导致对诱导的Lagrange乘数的自然解释。在此过程中，我们大大扩展了冯·斯坦格尔（Von Stengel）和科勒（GEB`97）引起的对抗（正常形式）团队游戏中最佳政策的重要特征。

我们在无限地平线上享受多智能经纪增强学习（Marl）零汇率马尔可夫游戏。我们专注于分散的Marl的实用性但具有挑战性的环境，其中代理人在没有集中式控制员的情况下做出决定，但仅根据自己的收益和当地行动进行了协调。代理商不需要观察对手的行为或收益，可能甚至不忘记对手的存在，也不得意识到基础游戏的零金额结构，该环境也称为学习文学中的彻底解散游戏。在本文中，我们开发了一种彻底的解耦Q学习动态，既合理和收敛则：当对手遵循渐近静止战略时，学习动态会收敛于对对手战略的最佳反应;当两个代理采用学习动态时，它们会收敛到游戏的纳什均衡。这种分散的环境中的关键挑战是从代理商的角度来看环境的非公平性，因为她自己的回报和系统演变都取决于其他代理人的行为，每个代理商同时和独立地互补她的政策。要解决此问题，我们开发了两个时间尺度的学习动态，每个代理会更新她的本地Q函数和value函数估计，后者在较慢的时间内发生。

最近，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的技术。

The extragradient method has recently gained increasing attention, due to its convergence behavior on smooth games. In $n$-player differentiable games, the eigenvalues of the Jacobian of the vector field are distributed on the complex plane, exhibiting more convoluted dynamics compared to classical (i.e., single player) minimization. In this work, we take a polynomial-based analysis of the extragradient with momentum for optimizing games with \emph{cross-shaped} Jacobian spectrum on the complex plane. We show two results. First, based on the hyperparameter setup, the extragradient with momentum exhibits three different modes of convergence: when the eigenvalues are distributed $i)$ on the real line, $ii)$ both on the real line along with complex conjugates, and $iii)$ only as complex conjugates. Then, we focus on the case $ii)$, i.e., when the eigenvalues of the Jacobian have \emph{cross-shaped} structure, as observed in training generative adversarial networks. For this problem class, we derive the optimal hyperparameters of the momentum extragradient method, and show that it achieves an accelerated convergence rate.

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.

Mean-field games have been used as a theoretical tool to obtain an approximate Nash equilibrium for symmetric and anonymous $N$-player games in literature. However, limiting applicability, existing theoretical results assume variations of a "population generative model", which allows arbitrary modifications of the population distribution by the learning algorithm. Instead, we show that $N$ agents running policy mirror ascent converge to the Nash equilibrium of the regularized game within $\tilde{\mathcal{O}}(\varepsilon^{-2})$ samples from a single sample trajectory without a population generative model, up to a standard $\mathcal{O}(\frac{1}{\sqrt{N}})$ error due to the mean field. Taking a divergent approach from literature, instead of working with the best-response map we first show that a policy mirror ascent map can be used to construct a contractive operator having the Nash equilibrium as its fixed point. Next, we prove that conditional TD-learning in $N$-agent games can learn value functions within $\tilde{\mathcal{O}}(\varepsilon^{-2})$ time steps. These results allow proving sample complexity guarantees in the oracle-free setting by only relying on a sample path from the $N$ agent simulator. Furthermore, we demonstrate that our methodology allows for independent learning by $N$ agents with finite sample guarantees.

我们研究了随机游戏（SGS）的梯度播放算法的性能，其中每个代理商试图通过基于代理之间共享的当前状态信息来独立做出决策来最大限度地提高自己的总折扣奖励。通过在给定状态下选择某个动作的概率来直接参数化策略。我们展示了纳什均衡（NES）和一阶固定政策在此设置中等同，并在严格的NES周围给出局部收敛速度。此外，对于称为马尔可夫潜在游戏的SGS的子类（包括具有重要特殊情况的代理中具有相同奖励的协作设置），我们设计了一种基于样本的增强学习算法，并为两者提供非渐近全局收敛速度分析精确的梯度游戏和我们基于样本的学习算法。我们的结果表明，迭代的数量达到$ \ epsilon $ -Ne线性缩放，而不是指数级，而代理人数。还考虑了局部几何和局部稳定性，在那里我们证明严格的NE是总潜在功能的局部最大值，完全混合的NE是鞍点。

当学习者与其他优化代理进行连续游戏时，我们研究了遗憾最小化的问题：在这种情况下，如果所有玩家都遵循一种无重组算法，则相对于完全对手环境，可能会达到较低的遗憾。我们在变异稳定的游戏（包括所有凸孔和单调游戏的连续游戏）的背景下研究了这个问题，当玩家只能访问其个人回报梯度时。如果噪音是加性的，那么游戏理论和纯粹的对抗性设置也会获得类似的遗憾保证。但是，如果噪声是乘法的，我们表明学习者实际上可以持续遗憾。我们通过学习速率分离的乐观梯度方案实现了更快的速度 - 也就是说，该方法的外推和更新步骤被调整为不同的时间表，具体取决于噪声配置文件。随后，为了消除对精致的超参数调整的需求，我们提出了一种完全自适应的方法，可以在最坏的和最佳案例的遗憾保证之间平稳地插入。