在这项研究中，我们考虑了两个玩家零和游戏中的正规领导者（FTRL）动力学的变体。在时间平衡策略时，FTRL保证会融合到NASH平衡，而许多变体都遭受了极限自行车行为的问题，即缺乏最后的介质收敛保证。为此，我们提出了一种突变FTRL（M-FTRL），该算法引入了用于动作概率扰动的突变。然后，我们研究了M-FTRL的连续时间动力学，并提供了强大的收敛保证，可以向固定点提供近似于NASH平衡的固定点。此外，我们的仿真表明，M-FTRL比FTRL和乐观的FTRL在全信息反馈下享有更快的收敛速度，并且在强盗反馈下表现出明显的收敛性。

游戏中的学习理论在AI社区中很突出，这是由多个不断上升的应用程序（例如多代理增强学习和生成对抗性网络）的动机。我们提出了突变驱动的乘法更新（M2WU），以在两人零和零正常形式游戏中学习平衡，并证明它在全面和嘈杂的信息反馈设置中都表现出了最后的题融合属性。在全信息反馈设置中，玩家观察了实用程序功能的确切梯度向量。另一方面，在嘈杂的信息反馈设置中，他们只能观察到嘈杂的梯度向量。现有的算法，包括众所周知的乘法权重更新（MWU）和乐观的MWU（OMWU）算法，未能收敛到具有嘈杂的信息反馈的NASH平衡。相反，在两个反馈设置中，M2WU表现出最后的近期收敛到NASH平衡附近的固定点。然后，我们证明它通过迭代地适应突变项来收敛到精确的NASH平衡。我们从经验上确认，M2WU在可剥削性和收敛速率方面胜过MWU和OMWU。

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.

在博弈论中的精髓结果是von Neumann的Minmax定理，这些定理使得零和游戏承认基本上独特的均衡解决方案。古典学习结果对本定理构建，以表明在线无后悔动态会聚到零和游戏中的时间平均意义上的均衡。在过去几年中，一个关键的研究方向专注于表征这种动态的日常行为。一般结果在这个方向上表明，广泛的在线学习动态是循环的，并且在零和游戏中正式的Poincar {e}复发。在具有时间不变均衡的定期零和游戏的情况下，我们分析了这些在线学习行为的稳健性。该模型概括了通常的重复游戏制定，同时也是参与者之间反复竞争的现实和自然模型，这取决于外源性环境变化，如日期效果，周到一周的趋势和季节性。有趣的是，即使在最简单的这种情况下，也可能失败的时间平均收敛性，尽管有均衡是固定的。相比之下，使用新颖的分析方法，我们表明Poincar \'{E}尽管这些动态系统的复杂性，非自主性质，但是普及的复发概括。

主导的行动是自然的（也许是最简单的）多代理概括的子最优动作，如标准单代理决策中的那样。因此类似于标准强盗学习，多代理系统中的基本学习问题是如果他们只能观察到他们播放动作的回报的嘈杂的强盗反馈，那么代理商可以学会有效地消除所有主导的动作。令人惊讶的是，尽管有一个看似简单的任务，我们展示了一个相当负面的结果;也就是说，标准没有遗憾的算法 - 包括整个双平均算法的家庭 - 可呈指数级地取消逐渐消除所有主导的行动。此外，具有较强的交换后悔的算法也遭受了类似的指数低效率。为了克服这些障碍，我们开发了一种新的算法，调整EXP3，历史奖励减少（exp3-DH）; Exp3-DH逐渐忘记仔细量身定制的速率。我们证明，当所有代理运行Exp3-DH（A.K.A.，在多代理学习中自行发行）时，所有主导的行动都可以在多项多轮内迭代地消除。我们的实验结果进一步证明了Exp3-DH的效率，即使是那些专门用于在游戏中学习的最先进的强盗算法，也无法有效地消除所有主导的行动。

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

我们展示了一种新颖的虚构播放动态变种，将经典虚拟游戏与Q学习进行随机游戏，分析其在双球零点随机游戏中的收敛性。我们的动态涉及在对手战略上形成信仰的球员以及他们自己的延续支付（Q-Function），并通过使用估计的延续收益来扮演贪婪的最佳回应。玩家从对对手行动的观察开始更新他们的信仰。学习动态的一个关键属性是，更新Q函数的信念发生在较慢的时间上，而不是对策略的信念的更新。我们在基于模型和无模式的情况下（不了解播放器支付功能和国家过渡概率），对策略的信念会聚到零和随机游戏的固定混合纳什均衡。

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

在拍卖领域，了解重复拍卖中学习动态的收敛属性是一个及时，重要的问题，例如在线广告市场中有许多应用程序。这项工作着重于重复的首次价格拍卖，该物品具有固定值的竞标者学会使用基于平均值的算法出价 - 大量的在线学习算法，其中包括流行的无regret算法，例如多重权重更新，并遵循扰动的领导者。我们完全表征了基于均值算法的学习动力学，从收敛到拍卖的NASH平衡方面，具有两种感觉：（1）时间平均水平：竞标者在bidiper the NASH平衡方面的回合分数，在极限中均在极限中。 ; （2）最后一题：竞标者的混合策略概况接近限制的NASH平衡。具体而言，结果取决于最高值的投标人的数量： - 如果数量至少为三个，则竞标动力学几乎可以肯定地收敛到拍卖的NASH平衡，无论是在时间平时还是在最后近期的情况下。 - 如果数字为两个，则竞标动力学几乎可以肯定会在时间平时收敛到NASH平衡，但不一定在最后近期。 - 如果数字是一个，则竞标动力学可能不会在时间平均值或最后近期的时间内收敛到NASH平衡。我们的发现为学习算法的融合动力学研究开辟了新的可能性。

在本文中，我们研究了具有约束策略空间的两人双线零和游戏。这种约束的自然发生的一个实例是使用混合策略，这与概率单纯限制相对应。我们提出和分析交替的镜面下降算法，其中每个玩家都会轮流采取镜子下降算法采取行动，以进行约束优化。我们将交替的镜像下降解释为双重空间中偏斜梯度流的交替离散化，并使用凸优化和修改能量功能的工具来建立$ O（k^{ - 2/3}）$绑定其平均后悔$ k $迭代。与同时版本的镜子下降算法相比，这可以定量验证该算法的更好行为，该算法的同时版本可以发散并产生$ O（k^{ - 1/2}）$平均遗憾。在不受约束的特殊情况下，我们的结果恢复了在（Bailey等人，Colt 2020）中研究的零和零游戏的交替梯度下降算法的行为。

本文研究了用于多机构增强学习的政策优化算法。我们首先在全信息设置中提出了针对两人零和零和马尔可夫游戏的算法框架，其中每次迭代均使用一个策略更新，使用某个矩阵游戏算法在每个状态下进行策略更新，并带有一个带有特定的值更新步骤学习率。该框架统一了许多现有和新的政策优化算法。我们表明，只要矩阵游戏算法在每种状态下，该算法的州平均策略会收敛到游戏的近似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 $层的简单游戏。

钢筋学习（RL）最近在许多人工智能应用中取得了巨大成功。 RL的许多最前沿应用涉及多个代理，例如，下棋和去游戏，自主驾驶和机器人。不幸的是，古典RL构建的框架不适合多代理学习，因为它假设代理的环境是静止的，并且没有考虑到其他代理的适应性。在本文中，我们介绍了动态环境中的多代理学习的随机游戏模型。我们专注于随机游戏的简单和独立学习动态的发展：每个代理商都是近视，并为其他代理商的战略选择最佳响应类型的行动，而不与对手进行任何协调。为随机游戏开发收敛最佳响应类型独立学习动态有限的进展。我们展示了我们最近提出的简单和独立的学习动态，可保证零汇率随机游戏的融合，以及对此设置中的动态多代理学习的其他同时算法的审查。一路上，我们还重新审视了博弈论和RL文学的一些古典结果，以适应我们独立的学习动态的概念贡献，以及我们分析的数学诺克特。我们希望这篇审查文件成为在博弈论中研究独立和自然学习动态的重新训练的推动力，对于具有动态环境的更具挑战性的环境。

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

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

最近有很多不可能的结果表明，在与对抗对手的马尔可夫游戏中最小化的遗憾在统计学上和计算上是棘手的。然而，这些结果都没有排除在所有各方采用相同学习程序的假设下，遗憾最小化的可能性。在这项工作中，我们介绍了第一种（据我们所知）在通用马尔可夫游戏中学习的算法，该算法在所有代理商执行时提供了sublinear后悔保证。我们获得的边界是为了置换遗憾，因此，在此过程中，意味着融合了相关的平衡。我们的算法是分散的，计算上有效的，并且不需要代理之间的任何通信。我们的主要观察结果是，在马尔可夫游戏中通过策略优化的在线学习基本上减少了一种加权遗憾的最小化形式，而未知权重由代理商的策略顺序的路径长度确定。因此，控制路径长度会导致加权的遗憾目标，以提供足够的适应性算法提供统一的后悔保证。

在本文中，我们调查了正规化的力量，即在解决广泛形式的游戏（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中。我们还提供数值结果来证实我们算法的优势。

我们研究了在两人零和马尔可夫游戏中找到NASH平衡的问题。由于其作为最小值优化程序的表述，解决该问题的自然方法是以交替的方式对每个玩家进行梯度下降/上升。但是，由于基本目标函数的非跨性别/非障碍性，该方法的理论理解是有限的。在我们的论文中，我们考虑解决马尔可夫游戏的熵登记变体。正则化将结构引入了优化景观中，从而使解决方案更加可识别，并允许更有效地解决问题。我们的主要贡献是表明，在正则化参数的正确选择下，梯度下降算法会收敛到原始未注册问题的NASH平衡。我们明确表征了我们算法的最后一个迭代的有限时间性能，该算法的梯度下降上升算法的现有收敛界限大大改善了而没有正则化。最后，我们通过数值模拟来补充分析，以说明算法的加速收敛性。

多代理系统的一个主要挑战是，系统的复杂性随着代理的数量以及其动作空间的规模而显着增长，在现实世界中，这是典型的，例如自动驾驶汽车，机器人团队，网络路由等。因此，正是在设计分散或独立算法的迫在眉睫的需求中，其中每个代理的更新仅基于它们的本地观察结果，而无需引入复杂的通信/协调机制。在这项工作中，我们研究了潜在游戏的独立熵规范化自然策略梯度（NPG）方法的有限时间收敛，在这些方法中，由于单方面偏差而导致的代理商效用函数的差异与普通潜在功能完全匹配。提出的熵注册的NPG方法使每个代理都可以根据自己的回报部署对称，分散和乘法更新。我们表明，所提出的方法以均方根速率收敛到定量响应平衡（QRE）（QRE）（QRE） - 与熵调制的游戏的平衡 - 与动作空间的大小无关，并且最多地与数字一起增长代理商。有吸引力的是，收敛率进一步与相同利益游戏的重要特殊情况的代理数量独立，从而导致了第一种以无维率收敛的方法。我们的方法可以用作平滑技术，以找到未注册问题的近似NASH平衡（NE），而无需假设固定策略是隔离的。

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

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