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

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

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

我们介绍并分析新的一阶优化算法系列，它概括并统一镜像血统和双平均。在该系列的框架内，我们定义了用于约束优化的新算法，这些算法结合了镜像血统和双平均的优点。我们的初步仿真研究表明，这些新算法在某些情况下显着优于可用方法。

我们考虑了一个$ n $ - 玩家随机游戏的子类，其中玩家在通过收益功能耦合时拥有自己的内部状态/动作空间。假定玩家的内部链是由独立过渡概率驱动的。此外，玩家只能收到其回报的实现，而不是实际功能，并且无法观察彼此的状态/行动。根据一些关于收益功能结构的假设，我们基于双重平均和双镜下降开发有效的学习算法，该算法几乎可以肯定地融合或预期$ \ epsilon $ nash $ nash平衡策略。特别是，我们根据游戏参数的多项式划分的迭代数量得出了上限，以实现$ \ epsilon $ -NASH平衡策略。除了马尔可夫潜在的游戏和线性季节随机游戏外，这项工作还提供了$ n $ - 玩家随机游戏的另一个子类，这些游戏可证明可以允许多项式学习算法找到其$ \ epsilon $ nash平衡策略。

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

本文重点介绍了静态和时变设置中决策依赖性分布的随机鞍点问题。这些是目标是随机收益函数的预期值，其中随机变量从分布图引起的分布中绘制。对于一般分布地图，即使已知分布是已知的，发现鞍点的问题也是一般的计算繁琐。为了实现易求解的解决方案方法，我们介绍了均衡点的概念 - 这是它们诱导的静止随机最小值问题的马鞍点 - 并为其存在和唯一性提供条件。我们证明，两个类解决方案之间的距离被界定，条件是该目标具有强凸强 - 凹入的收益和Lipschitz连续分布图。我们开发确定性和随机的原始算法，并证明它们对均衡点的收敛性。特别是，通过将来自随机梯度估计器的出现的错误建模为子-Weibull随机变量，我们提供期望的错误界限，并且在每个迭代的高概率中提供的误差;此外，我们向期望和几乎肯定地显示给社区的融合。最后，我们调查了分布地图的条件 - 我们调用相反的混合优势 - 确保目标是强烈的凸强 - 凹陷的。在这种假设下，我们表明原始双算法以类似的方式汇集到鞍座点。

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

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

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

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

几种广泛使用的一阶马鞍点优化方法将衍生天然衍生时的梯度下降成本（GDA）方法的相同连续时间常分等式（ODE）。然而，即使在简单的双线性游戏上，它们的收敛性也很差异。我们使用一种来自流体动力学的技术，称为高分辨率微分方程（HRDE）来设计几个骑马点优化方法的杂散。在双线性游戏中，派生HRDE的收敛性属性对应于起始离散方法的收敛性。使用这些技术，我们表明乐观梯度下降的HRDE具有最后迭代单调变分不等式的迭代收敛。据我们所知，这是第一个连续时间动态，用于收敛此类常规设置。此外，我们提供了ogda方法的最佳迭代收敛的速率，仅依靠单调运营商的一阶平滑度。

许多重要的学习算法，例如随机梯度方法，通常被部署以解决Riemannian歧管上的非线性问题。在这些应用中，我们提出了一个概括和扩展Robbins和Monro的精确随机近似框架的Riemannian算法家族。与他们的欧几里得对应物相比，由于歧管上缺乏全局线性结构，Riemannian迭代算法的理解要少得多。我们通过引入扩展的费米坐标框架来克服这一困难，该框架使我们能够绘制拟议的Riemannian Robbins-Monro（RRM）算法类别的渐近行为，以在基础歧管上非常轻微的假设下，在相关的确定性动力学系统下的算法。这样一来，我们提供了一个几乎肯定的收敛结果的一般模板，该模板镜像并扩展了欧几里得robbins-Monro方案的现有理论，尽管其分析要大得多，需要大量的新几何成分。我们通过使用该框架来建立基于回缩的类似物的融合来展示提出的RRM框架的灵活性，以解决最小化问题和游戏的流行乐观 /额外梯度方法，并且我们为其收敛提供了统一的处理。

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

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.

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

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

学习问题通常表现出一个有趣的反馈机制，其中人口数据对竞争决策者的行为作出反应。本文为这种现象制定了一种新的游戏理论框架，称为多人执行预测。我们专注于两个不同的解决方案概念，即（i）表现稳定稳定的均衡和（ii）纳什均衡的比赛。后者均衡可以说是更具信息性的，但只有在游戏是单调时才有效地发现。我们表明，在温和的假设下，可以通过各种算法有效地发现所需稳定的均衡，包括重复再培训和重复（随机）梯度播放。然后，我们为游戏的强大单调性建立透明的充分条件，并使用它们开发用于查找纳什均衡的算法。我们研究了衍生免费方法和自适应梯度算法，其中每个玩家在学习其分发和梯度步骤的学习的分配和梯度步骤之间交替。合成和半合成数值实验说明了结果。

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

我们开发了一种使用无遗憾的游戏动态解决凸面优化问题的算法框架。通过转换最小化凸起函数以顺序方式解决Min-Max游戏的辅助问题的问题，我们可以考虑一系列必须在另一个之后选择其行动的两名员工的一系列策略。这些策略的常见选择是所谓的无悔的学习算法，我们描述了许多此类并证明了遗憾。然后，我们表明许多凸面优化的经典一阶方法 - 包括平均迭代梯度下降，弗兰克 - 沃尔夫算法，重球算法和Nesterov的加速方法 - 可以被解释为我们框架的特殊情况由于每个玩家都做出正确选择无悔的策略。证明该框架中的收敛速率变得非常简单，因为它们遵循适当已知的遗憾范围。我们的框架还引发了一些凸优化的特殊情况的许多新的一阶方法。