最近，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 谷歌翻译
在本文中，我们建立了高效且取消耦合的学习动力学，因此，当由所有玩家在多人游戏中使用Perfect-Recall Inderfect Interfect Inderfection Formfortation Gartensive Games时，每个玩家的\ emph {触发后悔}会成长为$ o（\ log t t t t t t ）$ $ t $重复播放。这比$ o（t^{1/4}）$的先前最著名的触发regret键呈指数改进，并解决了Bai等人最近的一个开放问题。 （2022）。作为直接的结果，我们保证以$ \ frac {\ log log t} {t} $的接近速率以接近{粗相关的平衡}融合。基于先前的工作，我们的构造核心是关于从\ emph {polyenmial genter}衍生的固定点的更一般的结果，这是我们为\ emph {（粗）触发偏差函数建立的属性}。此外，我们的构造利用了凸壳的精制\ textit {遗憾电路}，与先验保证不同 - 保留了Syrgkanis等人引入的\ emph {rvu属性}。 （NIPS，2015年）；这种观察对基于CFR型遗憾的分解，在学习动态下建立近乎最佳的遗憾具有独立的兴趣。
translated by 谷歌翻译
最近的一项工作已经建立了未耦合的学习动力学，以至于当所有玩家在游戏中使用所有玩家时，每个玩家的\ emph {sorex} $ t $ recretitions在$ t $中增长了polygarithmarithm，这是$ t $的指数改进，比指数级的改进，比传统的保证在无缩写框架。但是，到目前为止，这些结果仅限于具有结构化策略空间的某些类别的游戏，例如正常形式和广泛形式的游戏。关于$ o（\ text {polylog} t）$遗憾界限是否可以为一般凸和紧凑型策略集获得的问题 - 这在经济学和多种系统中的许多基本模型中都发生 - 同时保留有效的策略更新是一种重要的问题。在本文中，我们通过建立$ o（\ log t）$ player后悔的第一个未耦合学习算法来回答这一点凸和紧凑的策略集。我们的学习动力基于对适当的\ emph {升起}空间的乐观跟随领导者的实例化，使用\ emph {self-condcordant正规器}，这是特殊的，这不是可行区域的障碍。此外，我们的学习动力是可以有效地实现的，如果可以访问登录策略的近端甲骨文，从而导致$ o（\ log \ log \ log t）$ ter-ter-ter-tir-tir-tir-tir-tir-tir-tir-tir-tir-tir-tir-tir-tirceptimity;当仅假设仅对\ emph {Linear}优化Oracle访问时，我们还会给出扩展。最后，我们调整动力学以保证对抗性制度中的$ O（\ sqrt {t}）$遗憾。即使在适用先前结果的特殊情况下，我们的算法也会改善最先进的遗憾界限，无论是依赖迭代次数还是对策略集的维度的依赖。
translated by 谷歌翻译
本文研究了用于多机构增强学习的政策优化算法。我们首先在全信息设置中提出了针对两人零和零和马尔可夫游戏的算法框架，其中每次迭代均使用一个策略更新，使用某个矩阵游戏算法在每个状态下进行策略更新，并带有一个带有特定的值更新步骤学习率。该框架统一了许多现有和新的政策优化算法。我们表明，只要矩阵游戏算法在每种状态下，该算法的州平均策略会收敛到游戏的近似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 $层的简单游戏。
translated by 谷歌翻译
最近有很多不可能的结果表明，在与对抗对手的马尔可夫游戏中最小化的遗憾在统计学上和计算上是棘手的。然而，这些结果都没有排除在所有各方采用相同学习程序的假设下，遗憾最小化的可能性。在这项工作中，我们介绍了第一种（据我们所知）在通用马尔可夫游戏中学习的算法，该算法在所有代理商执行时提供了sublinear后悔保证。我们获得的边界是为了置换遗憾，因此，在此过程中，意味着融合了相关的平衡。我们的算法是分散的，计算上有效的，并且不需要代理之间的任何通信。我们的主要观察结果是，在马尔可夫游戏中通过策略优化的在线学习基本上减少了一种加权遗憾的最小化形式，而未知权重由代理商的策略顺序的路径长度确定。因此，控制路径长度会导致加权的遗憾目标，以提供足够的适应性算法提供统一的后悔保证。
translated by 谷歌翻译
我们研究了非参数在线回归中的快速收敛速度，即遗憾的是关于具有有界复杂度的任意函数类来定义后悔。我们的贡献是两倍： - 在绝对损失中的非参数网上回归的可实现设置中，我们提出了一种随机适当的学习算法，该算法在假设类的顺序脂肪破碎尺寸方面获得了近乎最佳的错误。在与一类Littlestone维度$ D $的在线分类中，我们的绑定减少到$ d \ cdot {\ rm poly} \ log t $。这结果回答了一个问题，以及适当的学习者是否可以实现近乎最佳错误的界限;以前，即使在线分类，绑定的最知名错误也是$ \ tilde o（\ sqrt {dt}）$。此外，对于真实值（回归）设置，在这项工作之前，界定的最佳错误甚至没有以不正当的学习者所知。 - 使用上述结果，我们展示了Littlestone维度$ D $的一般总和二进制游戏的独立学习算法，每个玩家达到后悔$ \ tilde o（d ^ {3/4} \ cdot t ^ {1 / 4}）$。该结果概括了Syrgkanis等人的类似结果。 （2015）谁表明，在有限的游戏中，最佳遗憾可以从普通的o（\ sqrt {t}）$中的$ o（\ sqrt {t}）为游戏设置中的$ o（t ^ {1/4}）$。要建立上述结果，我们介绍了几种新技术，包括：分层聚合规则，以实现对实际类别的最佳错误，Hanneke等人的适当在线可实现学习者的多尺度扩展。 （2021），一种方法来表明这种非参数学习算法的输出是稳定的，并且证明Minimax定理在所有在线学习游戏中保持。
translated by 谷歌翻译
当学习者与其他优化代理进行连续游戏时，我们研究了遗憾最小化的问题：在这种情况下，如果所有玩家都遵循一种无重组算法，则相对于完全对手环境，可能会达到较低的遗憾。我们在变异稳定的游戏（包括所有凸孔和单调游戏的连续游戏）的背景下研究了这个问题，当玩家只能访问其个人回报梯度时。如果噪音是加性的，那么游戏理论和纯粹的对抗性设置也会获得类似的遗憾保证。但是，如果噪声是乘法的，我们表明学习者实际上可以持续遗憾。我们通过学习速率分离的乐观梯度方案实现了更快的速度 - 也就是说，该方法的外推和更新步骤被调整为不同的时间表，具体取决于噪声配置文件。随后，为了消除对精致的超参数调整的需求，我们提出了一种完全自适应的方法，可以在最坏的和最佳案例的遗憾保证之间平稳地插入。
translated by 谷歌翻译
计算NASH平衡策略是多方面强化学习中的一个核心问题，在理论和实践中都受到广泛关注。但是，到目前为止，可证明的保证金仅限于完全竞争性或合作的场景，或者在大多数实际应用中实现难以满足的强大假设。在这项工作中，我们通过调查Infinite-Horizon \ Emph {对抗性团队Markov Games}，这是一场自然而充分动机的游戏，其中一组相同兴奋的玩家 - 在没有任何明确的情况下，这是一个自然而有动机的游戏，这是一场自然而有动机的游戏，而偏离了先前的结果。协调或交流 - 正在与对抗者竞争。这种设置允许对零和马尔可夫潜在游戏进行统一处理，并作为模拟更现实的战略互动的一步，这些互动具有竞争性和合作利益。我们的主要贡献是第一种计算固定$ \ epsilon $ - Approximate Nash Equilibria在对抗性团队马尔可夫游戏中具有计算复杂性的算法，在游戏的所有自然参数中都是多项式的，以及$ 1/\ epsilon $。拟议的算法特别自然和实用，它基于为团队中的每个球员执行独立的政策梯度步骤，并与对手侧面的最佳反应同时；反过来，通过解决精心构造的线性程序来获得对手的政策。我们的分析利用非标准技术来建立具有非convex约束的非线性程序的KKT最佳条件，从而导致对诱导的Lagrange乘数的自然解释。在此过程中，我们大大扩展了冯·斯坦格尔（Von Stengel）和科勒（GEB`97）引起的对抗（正常形式）团队游戏中最佳政策的重要特征。
translated by 谷歌翻译
Imperfect information games (IIG) are games in which each player only partially observes the current game state. We study how to learn $\epsilon$-optimal strategies in a zero-sum IIG through self-play with trajectory feedback. We give a problem-independent lower bound $\mathcal{O}(H(A_{\mathcal{X}}+B_{\mathcal{Y}})/\epsilon^2)$ on the required number of realizations to learn these strategies with high probability, where $H$ is the length of the game, $A_{\mathcal{X}}$ and $B_{\mathcal{Y}}$ are the total number of actions for the two players. We also propose two Follow the Regularize leader (FTRL) algorithms for this setting: Balanced-FTRL which matches this lower bound, but requires the knowledge of the information set structure beforehand to define the regularization; and Adaptive-FTRL which needs $\mathcal{O}(H^2(A_{\mathcal{X}}+B_{\mathcal{Y}})/\epsilon^2)$ plays without this requirement by progressively adapting the regularization to the observations.
translated by 谷歌翻译
本文涉及两人零和马尔可夫游戏 - 可以说是多代理增强学习中最基本的设置 - 目的是学习纳什平衡（NE）的样本 - 优越。所有先前的结果至少都有两个障碍中的至少一个：多种试剂的诅咒和长层的障碍，无论使用采样方案如何。假设访问灵活的采样机制：生成模型，我们朝着解决此问题迈出了一步。专注于非平稳的有限 - 霍森马尔可夫游戏，我们开发了一种学习算法$ \ mathsf {nash} \ text { - } \ mathsf {q} \ text { - } \ text { - } \ mathsf {ftrl} $ and deflavery and Adaptive采样方案对抗性学习中的乐观原则（尤其是跟随规范化领导者（FTRL）方法），具有精致的奖励术语设计，可确保在FTRL动力学下进行某些可分解性。我们的算法使用$$ \ widetilde {o} \ bigg（\ frac {h^4 s（a+b）} {\ varepsilon^2} \ bigg）$ bigg）$ samples $ \ varepsilon $ -Approximate Markov ne策略其中$ s $是状态的数量，$ h $是地平线，而$ a $ a $ a $ a $ a $（resp。〜 $ b $）表示max-player的动作数（分别〜min-player）。从最小的意义上讲，这几乎无法得到解决。在此过程中，我们得出了一个精致的遗憾，以赋予FTRL的遗憾，从而明确说明了差异数量的作用，这可能具有独立的利益。
translated by 谷歌翻译
当今许多大型系统的设计，从交通路由环境到智能电网，都依赖游戏理论平衡概念。但是，随着$ n $玩家游戏的大小通常会随着$ n $而成倍增长，标准游戏理论分析实际上是不可行的。最近的方法通过考虑平均场游戏，匿名$ n $玩家游戏的近似值，在这种限制中，玩家的数量是无限的，而人口的状态分布，而不是每个单独的球员的状态，是兴趣。然而，迄今为止研究最多的平均场平衡的平均场nash平衡的实际可计算性通常取决于有益的非一般结构特性，例如单调性或收缩性能，这是已知的算法收敛所必需的。在这项工作中，我们通过开发均值相关和与粗相关的平衡的概念来研究平均场比赛的替代途径。我们证明，可以使用三种经典算法在\ emph {ash All Games}中有效地学习它们，而无需对游戏结构进行任何其他假设。此外，我们在文献中已经建立了对应关系，从而获得了平均场 - $ n $玩家过渡的最佳范围，并经验证明了这些算法在简单游戏中的收敛性。
translated by 谷歌翻译
在本文中，我们解决了普通游戏中无遗憾的学习问题。具体而言，我们提供了一种简单实用的算法，实现了固定的阶梯大小的恒定遗憾。随着阶梯大小的增加，我们的算法的累积遗憾可被线性降低。我们的调查结果离开了现行范式，即消失的阶梯尺寸是迄今为止所有最先进的方法的低遗憾的先决条件。通过定义我们称之为Clairvoyant乘法权重更新（CMWU）的小说算法，从此范例转移到此范式。 CMWU是配备有精神模型的乘法权重更新（MWU），其在下一个时期中的系统状态有关系统的状态。每个代理记录其混合策略，即它对在下一期间在下一期间播放的信念，在此共享心理模型中，在此共享心理模型中使用MWU内部更新而没有对实际行为的任何改变，直到它平衡，从而标记其与第二天的真实结果一致。然后，只有那个代理在现实世界中采取行动，有效地在第二天的系统状态的“全面知识”，即它们是克莱师。CMWU有效充当MWU一天展望，实现有界遗憾。在技术水平，我们建立了任何选择的阶梯大小的自我一致的心理模型，并在其唯一性和线性时间计算的阶梯大小上提供界限收缩映射参数。我们的论点超越正常的游戏，几乎没有努力。
translated by 谷歌翻译
我们开发了一种使用无遗憾的游戏动态解决凸面优化问题的算法框架。通过转换最小化凸起函数以顺序方式解决Min-Max游戏的辅助问题的问题，我们可以考虑一系列必须在另一个之后选择其行动的两名员工的一系列策略。这些策略的常见选择是所谓的无悔的学习算法，我们描述了许多此类并证明了遗憾。然后，我们表明许多凸面优化的经典一阶方法 - 包括平均迭代梯度下降，弗兰克 - 沃尔夫算法，重球算法和Nesterov的加速方法 - 可以被解释为我们框架的特殊情况由于每个玩家都做出正确选择无悔的策略。证明该框架中的收敛速率变得非常简单，因为它们遵循适当已知的遗憾范围。我们的框架还引发了一些凸优化的特殊情况的许多新的一阶方法。
translated by 谷歌翻译
我们开发了一个统一的随机近似框架，用于分析游戏中多学院在线学习的长期行为。我们的框架基于“原始偶尔”，镜像的Robbins-Monro（MRM）模板，该模板涵盖了各种各样的流行游戏理论学习算法（梯度方法，乐观的变体，Exp3算法，用于基于付费的反馈，在有限游戏等中）。除了提供这些算法的综合视图外，提出的MRM蓝图还使我们能够在连续和有限的游戏中获得渐近和有限时间的广泛新收敛结果。
translated by 谷歌翻译
主导的行动是自然的（也许是最简单的）多代理概括的子最优动作，如标准单代理决策中的那样。因此类似于标准强盗学习，多代理系统中的基本学习问题是如果他们只能观察到他们播放动作的回报的嘈杂的强盗反馈，那么代理商可以学会有效地消除所有主导的动作。令人惊讶的是，尽管有一个看似简单的任务，我们展示了一个相当负面的结果;也就是说，标准没有遗憾的算法 - 包括整个双平均算法的家庭 - 可呈指数级地取消逐渐消除所有主导的行动。此外，具有较强的交换后悔的算法也遭受了类似的指数低效率。为了克服这些障碍，我们开发了一种新的算法，调整EXP3，历史奖励减少（exp3-DH）; Exp3-DH逐渐忘记仔细量身定制的速率。我们证明，当所有代理运行Exp3-DH（A.K.A.，在多代理学习中自行发行）时，所有主导的行动都可以在多项多轮内迭代地消除。我们的实验结果进一步证明了Exp3-DH的效率，即使是那些专门用于在游戏中学习的最先进的强盗算法，也无法有效地消除所有主导的行动。
translated by 谷歌翻译
在本文中，我们调查了正规化的力量，即在解决广泛形式的游戏（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中。我们还提供数值结果来证实我们算法的优势。
translated by 谷歌翻译
我们考虑在具有强盗反馈的未知游戏中的在线无遗憾的学习，其中每个代理只在每次都观察到其奖励 - 所有参与者当前的联合行动 - 而不是其渐变。我们专注于平稳且强烈单调的游戏类，并在其中研究最佳的无遗憾。利用自我协调的障碍功能，我们首先构建在线强盗凸优化算法，并表明它实现了平滑且强烈 - 凹陷的支付下$ \ tilde {\ theta}（\ sqrt {t}）$的单代理最佳遗憾职能。然后，如果每个代理在强烈单调的游戏中应用这种无悔的学习算法，则以$ \ tilde {\ theta}的速率，联合动作会收敛于\ texit {last erate}到唯一的纳什均衡（1 / \ sqrt {t}）$。在我们的工作之前，同一类游戏中的最熟悉的融合率是$ O（1 / T ^ {1/3}）$（通过不同的算法实现），从而留下了最佳无悔的问题学习算法（因为已知的下限为$ \ omega（1 / \ sqrt {t}）$）。我们的结果因此通过识别第一双重最佳强盗学习算法来解决这个公开问题并促进强盗游戏 - 理论学习的广泛景观，因为它达到了（达到了日志因子）单王子学习和最佳的最佳遗憾多代理学习中的最后迭代收敛速度。我们还展示了几项模拟研究的结果 - Cournot竞争，凯利拍卖和分布式正则化物流回归 - 以证明我们算法的功效。
translated by 谷歌翻译
在拍卖领域，了解重复拍卖中学习动态的收敛属性是一个及时，重要的问题，例如在线广告市场中有许多应用程序。这项工作着重于重复的首次价格拍卖，该物品具有固定值的竞标者学会使用基于平均值的算法出价 - 大量的在线学习算法，其中包括流行的无regret算法，例如多重权重更新，并遵循扰动的领导者。我们完全表征了基于均值算法的学习动力学，从收敛到拍卖的NASH平衡方面，具有两种感觉：（1）时间平均水平：竞标者在bidiper the NASH平衡方面的回合分数，在极限中均在极限中。 ; （2）最后一题：竞标者的混合策略概况接近限制的NASH平衡。具体而言，结果取决于最高值的投标人的数量： - 如果数量至少为三个，则竞标动力学几乎可以肯定地收敛到拍卖的NASH平衡，无论是在时间平时还是在最后近期的情况下。 - 如果数字为两个，则竞标动力学几乎可以肯定会在时间平时收敛到NASH平衡，但不一定在最后近期。 - 如果数字是一个，则竞标动力学可能不会在时间平均值或最后近期的时间内收敛到NASH平衡。我们的发现为学习算法的融合动力学研究开辟了新的可能性。
translated by 谷歌翻译
我们研究了马尔可夫潜在游戏（MPG）中多机构增强学习（RL）问题的策略梯度方法的全球非反应收敛属性。要学习MPG的NASH平衡，在该MPG中，状态空间的大小和/或玩家数量可能非常大，我们建议使用TANDEM所有玩家运行的新的独立政策梯度算法。当梯度评估中没有不确定性时，我们表明我们的算法找到了$ \ epsilon $ -NASH平衡，$ o（1/\ epsilon^2）$迭代复杂性并不明确取决于状态空间大小。如果没有确切的梯度，我们建立$ O（1/\ epsilon^5）$样品复杂度在潜在的无限大型状态空间中，用于利用函数近似的基于样本的算法。此外，我们确定了一类独立的政策梯度算法，这些算法都可以融合零和马尔可夫游戏和马尔可夫合作游戏，并与玩家不喜欢玩的游戏类型。最后，我们提供了计算实验来证实理论发展的优点和有效性。
translated by 谷歌翻译
我们证明，乐观的循环范围的领导者（oftrl）以及平滑的价值更新，发现了一个$ o（t^{ - 1}）$ - $ t tum迭代中的nash平衡，用于两种播放器零 - 总和马尔可夫游戏提供完整的信息。这改善了$ \ tilde {o}（t^{ - 5/6}）$收敛率最近在Paper Zhang等人（2022）中显示。精致的分析取决于两种基本要素。首先，在马尔可夫游戏中，这两个玩家的遗憾虽然不一定像普通形式的游戏一样不受负责。该属性使我们能够绑定学习动力学的二阶路径长度。其次，我们证明了对Oftrl部署的权重剃须的额外的$ \ log t $因子的权重。这种至关重要的改进实现了导致最终$ O（t^{ - 1}）$ rate的归纳分析。
translated by 谷歌翻译