随机游戏的学习可以说是多功能钢筋学习(MARL)中最标准和最基本的环境。在本文中,我们考虑在非渐近制度的随机游戏中分散的Marl。特别是,我们在大量的一般总和随机游戏(SGS)中建立了完全分散的Q学习算法的有限样本复杂性 - 弱循环SGS,包括对所有代理商的普通合作MARL设置具有相同的奖励(马尔可夫团队问题是一个特例。我们专注于实用的同时具有挑战性地设置完全分散的Marl,既不奖励也没有其他药剂的作用,每个试剂都可以观察到。事实上,每个特工都完全忘记了其他决策者的存在。表格和线性函数近似情况都已考虑。在表格设置中,我们分析了分散的Q学习算法的样本复杂性,以收敛到马尔可夫完美均衡(NASH均衡)。利用线性函数近似,结果用于收敛到线性近似平衡 - 我们提出的均衡的新概念 - 这描述了每个代理的策略是线性空间内的最佳回复(到其他代理)。还提供了数值实验,用于展示结果。
translated by 谷歌翻译
我们研究了随机游戏(SGS)的梯度播放算法的性能,其中每个代理商试图通过基于代理之间共享的当前状态信息来独立做出决策来最大限度地提高自己的总折扣奖励。通过在给定状态下选择某个动作的概率来直接参数化策略。我们展示了纳什均衡(NES)和一阶固定政策在此设置中等同,并在严格的NES周围给出局部收敛速度。此外,对于称为马尔可夫潜在游戏的SGS的子类(包括具有重要特殊情况的代理中具有相同奖励的协作设置),我们设计了一种基于样本的增强学习算法,并为两者提供非渐近全局收敛速度分析精确的梯度游戏和我们基于样本的学习算法。我们的结果表明,迭代的数量达到$ \ epsilon $ -Ne线性缩放,而不是指数级,而代理人数。还考虑了局部几何和局部稳定性,在那里我们证明严格的NE是总潜在功能的局部最大值,完全混合的NE是鞍点。
translated by 谷歌翻译
我们研究了马尔可夫潜在游戏(MPG)中多机构增强学习(RL)问题的策略梯度方法的全球非反应收敛属性。要学习MPG的NASH平衡,在该MPG中,状态空间的大小和/或玩家数量可能非常大,我们建议使用TANDEM所有玩家运行的新的独立政策梯度算法。当梯度评估中没有不确定性时,我们表明我们的算法找到了$ \ epsilon $ -NASH平衡,$ o(1/\ epsilon^2)$迭代复杂性并不明确取决于状态空间大小。如果没有确切的梯度,我们建立$ O(1/\ epsilon^5)$样品复杂度在潜在的无限大型状态空间中,用于利用函数近似的基于样本的算法。此外,我们确定了一类独立的政策梯度算法,这些算法都可以融合零和马尔可夫游戏和马尔可夫合作游戏,并与玩家不喜欢玩的游戏类型。最后,我们提供了计算实验来证实理论发展的优点和有效性。
translated by 谷歌翻译
钢筋学习(RL)最近在许多人工智能应用中取得了巨大成功。 RL的许多最前沿应用涉及多个代理,例如,下棋和去游戏,自主驾驶和机器人。不幸的是,古典RL构建的框架不适合多代理学习,因为它假设代理的环境是静止的,并且没有考虑到其他代理的适应性。在本文中,我们介绍了动态环境中的多代理学习的随机游戏模型。我们专注于随机游戏的简单和独立学习动态的发展:每个代理商都是近视,并为其他代理商的战略选择最佳响应类型的行动,而不与对手进行任何协调。为随机游戏开发收敛最佳响应类型独立学习动态有限的进展。我们展示了我们最近提出的简单和独立的学习动态,可保证零汇率随机游戏的融合,以及对此设置中的动态多代理学习的其他同时算法的审查。一路上,我们还重新审视了博弈论和RL文学的一些古典结果,以适应我们独立的学习动态的概念贡献,以及我们分析的数学诺克特。我们希望这篇审查文件成为在博弈论中研究独立和自然学习动态的重新训练的推动力,对于具有动态环境的更具挑战性的环境。
translated by 谷歌翻译
我们在无限地平线上享受多智能经纪增强学习(Marl)零汇率马尔可夫游戏。我们专注于分散的Marl的实用性但具有挑战性的环境,其中代理人在没有集中式控制员的情况下做出决定,但仅根据自己的收益和当地行动进行了协调。代理商不需要观察对手的行为或收益,可能甚至不忘记对手的存在,也不得意识到基础游戏的零金额结构,该环境也称为学习文学中的彻底解散游戏。在本文中,我们开发了一种彻底的解耦Q学习动态,既合理和收敛则:当对手遵循渐近静止战略时,学习动态会收敛于对对手战略的最佳反应;当两个代理采用学习动态时,它们会收敛到游戏的纳什均衡。这种分散的环境中的关键挑战是从代理商的角度来看环境的非公平性,因为她自己的回报和系统演变都取决于其他代理人的行为,每个代理商同时和独立地互补她的政策。要解决此问题,我们开发了两个时间尺度的学习动态,每个代理会更新她的本地Q函数和value函数估计,后者在较慢的时间内发生。
translated by 谷歌翻译
我们与指定为领导者的球员之一和其他球员读为追随者的球员学习多人一般汇总马尔可夫游戏。特别是,我们专注于追随者是近视的游戏,即,他们的目标是最大限度地提高他们的瞬间奖励。对于这样的游戏,我们的目标是找到一个Stackelberg-Nash均衡(SNE),这是一个策略对$(\ pi ^ *,\ nu ^ *)$,这样(i)$ \ pi ^ * $是追随者始终发挥最佳回应的领导者的最佳政策,(ii)$ \ nu ^ * $是追随者的最佳反应政策,这是由$ \ pi ^ *引起的追随者游戏的纳什均衡$。我们开发了用于在线和离线设置中的SNE解决SNE的采样高效的强化学习(RL)算法。我们的算法是最小二乘值迭代的乐观和悲观的变体,并且它们很容易能够在大状态空间的设置中结合函数近似工具。此外,对于线性函数近似的情况,我们证明我们的算法分别在线和离线设置下实现了Sublinear遗憾和次优。据我们所知,我们建立了第一种可用于解决近代Markov游戏的SNES的第一款可透明的RL算法。
translated by 谷歌翻译
在多机构强化学习(MARL)中,独立学习者是那些不观察系统中其他代理商的行为的学习者。由于信息的权力下放,设计独立的学习者将发挥均匀的态度是有挑战性的。本文研究了使用满足动态来指导独立学习者在随机游戏中近似平衡的可行性。对于$ \ epsilon \ geq 0 $,$ \ epsilon $ -SATISFICING策略更新规则是任何规则,指示代理在$ \ epsilon $ best-best-reversponding to to to the其余参与者的策略时不要更改其策略; $ \ epsilon $ -SATISFIFICING路径定义为当每个代理使用某些$ \ epsilon $ -SATISFIFICING策略更新规则来选择其下一个策略时,获得的联合策略序列。我们建立了关于$ \ epsilon $ - 偏离型路径的结构性结果,这些路径是$ \ epsilon $ equilibium in Symmetric $ n $ - 玩家游戏和带有两个玩家的一般随机游戏。然后,我们为$ n $玩家对称游戏提出了一种独立的学习算法,并为自我玩法的$ \ epsilon $ equilibrium提供了高可能性保证。此保证仅使用对称性,利用$ \ epsilon $ satisficing路径的先前未开发的结构。
translated by 谷歌翻译
We study a multi-agent reinforcement learning (MARL) problem where the agents interact over a given network. The goal of the agents is to cooperatively maximize the average of their entropy-regularized long-term rewards. To overcome the curse of dimensionality and to reduce communication, we propose a Localized Policy Iteration (LPI) algorithm that provably learns a near-globally-optimal policy using only local information. In particular, we show that, despite restricting each agent's attention to only its $\kappa$-hop neighborhood, the agents are able to learn a policy with an optimality gap that decays polynomially in $\kappa$. In addition, we show the finite-sample convergence of LPI to the global optimal policy, which explicitly captures the trade-off between optimality and computational complexity in choosing $\kappa$. Numerical simulations demonstrate the effectiveness of LPI.
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 谷歌翻译
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.
translated by 谷歌翻译
计算NASH平衡策略是多方面强化学习中的一个核心问题,在理论和实践中都受到广泛关注。但是,到目前为止,可证明的保证金仅限于完全竞争性或合作的场景,或者在大多数实际应用中实现难以满足的强大假设。在这项工作中,我们通过调查Infinite-Horizo​​n \ Emph {对抗性团队Markov Games},这是一场自然而充分动机的游戏,其中一组相同兴奋的玩家 - 在没有任何明确的情况下,这是一个自然而有动机的游戏,这是一场自然而有动机的游戏,而偏离了先前的结果。协调或交流 - 正在与对抗者竞争。这种设置允许对零和马尔可夫潜在游戏进行统一处理,并作为模拟更现实的战略互动的一步,这些互动具有竞争性和合作利益。我们的主要贡献是第一种计算固定$ \ epsilon $ - Approximate Nash Equilibria在对抗性团队马尔可夫游戏中具有计算复杂性的算法,在游戏的所有自然参数中都是多项式的,以及$ 1/\ epsilon $。拟议的算法特别自然和实用,它基于为团队中的每个球员执行独立的政策梯度步骤,并与对手侧面的最佳反应同时;反过来,通过解决精心构造的线性程序来获得对手的政策。我们的分析利用非标准技术来建立具有非convex约束的非线性程序的KKT最佳条件,从而导致对诱导的Lagrange乘数的自然解释。在此过程中,我们大大扩展了冯·斯坦格尔(Von Stengel)和科勒(GEB`97)引起的对抗(正常形式)团队游戏中最佳政策的重要特征。
translated by 谷歌翻译
我们研究了平均奖励马尔可夫决策过程(AMDP)的问题,并开发了具有强大理论保证的新型一阶方法,以进行政策评估和优化。由于缺乏勘探,现有的彻底评估方法遭受了次优融合率以及处理不足的随机策略(例如确定性政策)的失败。为了解决这些问题,我们开发了一种新颖的差异时间差异(VRTD)方法,具有随机策略的线性函数近似以及最佳收敛保证,以及一种探索性方差降低的时间差(EVRTD)方法,用于不充分的随机策略,可相当的融合保证。我们进一步建立了政策评估偏见的线性收敛速率,这对于改善策略优化的总体样本复杂性至关重要。另一方面,与对MDP的政策梯度方法的有限样本分析相比,对AMDP的策略梯度方法的现有研究主要集中在基础马尔可夫流程的限制性假设下(例如,参见Abbasi-e, Yadkori等人,2019年),他们通常缺乏整体样本复杂性的保证。为此,我们开发了随机策略镜下降(SPMD)的平均奖励变体(LAN,2022)。我们建立了第一个$ \ widetilde {\ Mathcal {o}}(\ epsilon^{ - 2})$样品复杂性,用于在生成模型(带有UNICHAIN假设)和Markovian Noise模型(使用Ergodicicic Modele(具有核能的模型)下,使用策略梯度方法求解AMDP假设)。该界限可以进一步改进到$ \ widetilde {\ Mathcal {o}}}(\ epsilon^{ - 1})$用于求解正则化AMDPS。我们的理论优势通过数值实验来证实。
translated by 谷歌翻译
本文通过离线数据在两人零和马尔可夫游戏中学习NASH Equilibria的进展。具体而言,考虑使用$ S $州的$ \ gamma $ discousped Infinite-Horizo​​n Markov游戏,其中Max-player具有$ $ ACTIVE,而Min-player具有$ B $ Actions。我们提出了一种基于悲观模型的算法,具有伯恩斯坦风格的较低置信界(称为VI-LCB游戏),事实证明,该算法可以找到$ \ varepsilon $ - approximate-approximate nash平衡,带有样品复杂性,不大于$ \ frac {c_ {c_ {c_ {c_ { \ Mathsf {剪切}}}^{\ star} s(a+b)} {(1- \ gamma)^{3} \ varepsilon^{2}} $(最多到某个log factor)。在这里,$ c _ {\ mathsf {剪切}}}^{\ star} $是一些单方面剪接的浓缩系数,反映了可用数据的覆盖范围和分配变化(vis- \`a-vis目标数据),而目标是目标精度$ \ varepsilon $可以是$ \ big(0,\ frac {1} {1- \ gamma} \ big] $的任何值。我们的样本复杂性绑定了先前的艺术,以$ \ min \ {a, b \} $,实现整个$ \ varepsilon $ range的最小值最佳性。我们结果的一个吸引力的功能在于算法简单性,这揭示了降低方差降低和样本拆分的不必要性。
translated by 谷歌翻译
我们考虑在平均场比赛中在线加强学习。与现有作品相反,我们通过开发一种使用通用代理的单个样本路径来估算均值场和最佳策略的算法来减轻对均值甲骨文的需求。我们称此沙盒学习为其,因为它可以用作在多代理非合作环境中运行的任何代理商的温暖启动。我们采用了两种时间尺度的方法,在该方法中,平均场的在线固定点递归在较慢的时间表上运行,并与通用代理更快的时间范围内的控制策略更新同时进行。在足够的勘探条件下,我们提供有限的样本收敛保证,从平均场和控制策略融合到平均场平衡方面。沙盒学习算法的样本复杂性为$ \ Mathcal {o}(\ epsilon^{ - 4})$。最后,我们从经验上证明了沙盒学习算法在交通拥堵游戏中的有效性。
translated by 谷歌翻译
我们研究了在两人零和马尔可夫游戏中找到NASH平衡的问题。由于其作为最小值优化程序的表述,解决该问题的自然方法是以交替的方式对每个玩家进行梯度下降/上升。但是,由于基本目标函数的非跨性别/非障碍性,该方法的理论理解是有限的。在我们的论文中,我们考虑解决马尔可夫游戏的熵登记变体。正则化将结构引入了优化景观中,从而使解决方案更加可识别,并允许更有效地解决问题。我们的主要贡献是表明,在正则化参数的正确选择下,梯度下降算法会收敛到原始未注册问题的NASH平衡。我们明确表征了我们算法的最后一个迭代的有限时间性能,该算法的梯度下降上升算法的现有收敛界限大大改善了而没有正则化。最后,我们通过数值模拟来补充分析,以说明算法的加速收敛性。
translated by 谷歌翻译
Q学习长期以来一直是最受欢迎的强化学习算法之一,几十年来,Q学习的理论分析一直是一个活跃的研究主题。尽管对Q-学习的渐近收敛分析的研究具有悠久的传统,但非肿瘤收敛性直到最近才受到积极研究。本文的主要目的是通过控制系统的观点研究马尔可夫观察模型下异步Q学习的新有限时间分析。特别是,我们引入了Q学习的离散时间变化的开关系统模型,并减少了分析的步骤尺寸,这显着改善了使用恒定步骤尺寸的开关系统分析的最新开发,并导致\(\(\)(\) Mathcal {o} \ left(\ sqrt {\ frac {\ log k} {k}}} \ right)\)\)\)\)\)\)\)\)与大多数艺术状态相当或更好。同时,新应用了使用类似转换的技术,以避免通过减小的步骤尺寸提出的分析中的难度。提出的分析带来了其他见解,涵盖了不同的方案,并提供了新的简化模板,以通过其独特的连接与离散时间切换系统的独特联系来加深我们对Q学习的理解。
translated by 谷歌翻译
We consider learning approximate Nash equilibria for discrete-time mean-field games with nonlinear stochastic state dynamics subject to both average and discounted costs. To this end, we introduce a mean-field equilibrium (MFE) operator, whose fixed point is a mean-field equilibrium (i.e. equilibrium in the infinite population limit). We first prove that this operator is a contraction, and propose a learning algorithm to compute an approximate mean-field equilibrium by approximating the MFE operator with a random one. Moreover, using the contraction property of the MFE operator, we establish the error analysis of the proposed learning algorithm. We then show that the learned mean-field equilibrium constitutes an approximate Nash equilibrium for finite-agent games.
translated by 谷歌翻译
我们考虑在具有非线性函数近似的两名玩家零和马尔可夫游戏中学习NASH平衡,其中动作值函数通过繁殖内核Hilbert Space(RKHS)中的函数近似。关键挑战是如何在高维函数空间中进行探索。我们提出了一种新颖的在线学习算法,以最大程度地减少双重性差距来找到NASH平衡。我们算法的核心是基于不确定性的乐观原理得出的上和下置信度界限。我们证明,在非常温和的假设上,我们的算法能够获得$ O(\ sqrt {t})$遗憾,并在对奖励功能和马尔可夫游戏的基本动态下进行多项式计算复杂性。我们还提出了我们的算法的几个扩展,包括具有伯恩斯坦型奖励的算法,可以实现更严格的遗憾,以及用于模型错误指定的另一种算法,可以应用于神经功能近似。
translated by 谷歌翻译
具有很多玩家的非合作和合作游戏具有许多应用程序,但是当玩家数量增加时,通常仍然很棘手。由Lasry和Lions以及Huang,Caines和Malham \'E引入的,平均野外运动会(MFGS)依靠平均场外近似值,以使玩家数量可以成长为无穷大。解决这些游戏的传统方法通常依赖于以完全了解模型的了解来求解部分或随机微分方程。最近,增强学习(RL)似乎有望解决复杂问题。通过组合MFGS和RL,我们希望在人口规模和环境复杂性方面能够大规模解决游戏。在这项调查中,我们回顾了有关学习MFG中NASH均衡的最新文献。我们首先确定最常见的设置(静态,固定和进化)。然后,我们为经典迭代方法(基于最佳响应计算或策略评估)提供了一个通用框架,以确切的方式解决MFG。在这些算法和与马尔可夫决策过程的联系的基础上,我们解释了如何使用RL以无模型的方式学习MFG解决方案。最后,我们在基准问题上介绍了数值插图,并以某些视角得出结论。
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 谷歌翻译