我们暴露了在离线多代理增强学习（MARL）中奖励中毒的危险，从而使攻击者可以在离线数据集中对不同学习者的奖励向量修改，同时又产生了中毒成本。基于中毒的数据集，所有使用一些基于信心的MARL算法的理性学习者将推断出，目标政策 - 攻击者选择的目标政策最初是解决方案概念 - 是马尔可夫的完美主要策略，用于基础马尔可夫游戏因此，他们将来将采用这种潜在的破坏目标政策。我们表征了攻击者可以安装目标策略的确切条件。我们进一步展示了攻击者如何制定线性程序以最大程度地减少其中毒成本。我们的工作表明需要强大的泥土反对对抗攻击。

我们与指定为领导者的球员之一和其他球员读为追随者的球员学习多人一般汇总马尔可夫游戏。特别是，我们专注于追随者是近视的游戏，即，他们的目标是最大限度地提高他们的瞬间奖励。对于这样的游戏，我们的目标是找到一个Stackelberg-Nash均衡（SNE），这是一个策略对$（\ pi ^ *，\ nu ^ *）$，这样（i）$ \ pi ^ * $是追随者始终发挥最佳回应的领导者的最佳政策，（ii）$ \ nu ^ * $是追随者的最佳反应政策，这是由$ \ pi ^ *引起的追随者游戏的纳什均衡$。我们开发了用于在线和离线设置中的SNE解决SNE的采样高效的强化学习（RL）算法。我们的算法是最小二乘值迭代的乐观和悲观的变体，并且它们很容易能够在大状态空间的设置中结合函数近似工具。此外，对于线性函数近似的情况，我们证明我们的算法分别在线和离线设置下实现了Sublinear遗憾和次优。据我们所知，我们建立了第一种可用于解决近代Markov游戏的SNES的第一款可透明的RL算法。

我们研究奖励设计策略，用于激励加强学习代理，从一系列可接受的政策中采用政策。奖励设计师的目标是经济高效地修改底层奖励功能，同时确保在新奖励功能下的任何大约最佳的确定性政策是可允许的，并且在原始奖励功能下执行良好。这个问题可以被视为最佳奖励中毒攻击问题的双重问题：而不是强制代理商采用特定的政策，而奖励设计师则激励一个代理人以避免采取某些州不可受理的行动。也许令人惊讶的是，与最佳奖励中毒攻击的问题相比，我们首先表明可允许的政策教学的奖励设计问题是在计算上具有挑战性的，并且难以找到近似最佳的奖励修改。然后，我们通过制定最佳解决方案的代理问题，其最佳解决方案近似于我们的环境中奖励设计问题的最佳解决方案，但更适用于优化技术和分析。对于此替代问题，我们呈现了在最佳解决方案的值上提供限制的表征结果。最后，我们设计了一个本地搜索算法来解决代理问题，并使用基于模拟的实验展示其实用程序。

我们考虑了有多个具有不同奖励功能的利益相关者的情节强化学习问题。我们的目标是输出有关不同奖励功能在社会上公平的政策。先前的工作提出了不同的目标，即公平政策必须优化，包括最低福利和广义的基尼福利。我们首先对问题进行公理视图，并提出四个公理，任何这样的公平目标都必须满足。我们表明，纳什社会福利是一个独特的目标，它独特地满足了所有四个目标，而先前的目标无法满足所有四个公理。然后，我们考虑了基础模型，即马尔可夫决策过程未知的问题的学习版本。我们考虑到最大程度地降低对公平政策最大化的遗憾的问题，从而最大化三个不同的公平目标 - 最低限度的福利，广义基尼福利和纳什社会福利。基于乐观的计划，我们提出了一种通用的学习算法，并在三种不同的政策方面得出了遗憾。为了纳什社会福利的目的，我们还遗憾地得出了一个遗憾的遗憾，它以$ n $（代理的数量）成倍增长。最后，我们表明，为了最低限度福利的目的，对于较弱的遗憾概念，人们可以将遗憾提高到$ o（h）$。

We study episodic two-player zero-sum Markov games (MGs) in the offline setting, where the goal is to find an approximate Nash equilibrium (NE) policy pair based on a dataset collected a priori. When the dataset does not have uniform coverage over all policy pairs, finding an approximate NE involves challenges in three aspects: (i) distributional shift between the behavior policy and the optimal policy, (ii) function approximation to handle large state space, and (iii) minimax optimization for equilibrium solving. We propose a pessimism-based algorithm, dubbed as pessimistic minimax value iteration (PMVI), which overcomes the distributional shift by constructing pessimistic estimates of the value functions for both players and outputs a policy pair by solving NEs based on the two value functions. Furthermore, we establish a data-dependent upper bound on the suboptimality which recovers a sublinear rate without the assumption on uniform coverage of the dataset. We also prove an information-theoretical lower bound, which suggests that the data-dependent term in the upper bound is intrinsic. Our theoretical results also highlight a notion of "relative uncertainty", which characterizes the necessary and sufficient condition for achieving sample efficiency in offline MGs. To the best of our knowledge, we provide the first nearly minimax optimal result for offline MGs with function approximation.

本文通过离线数据在两人零和马尔可夫游戏中学习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的最小值最佳性。我们结果的一个吸引力的功能在于算法简单性，这揭示了降低方差降低和样本拆分的不必要性。

本文涉及两人零和马尔可夫游戏 - 可以说是多代理增强学习中最基本的设置 - 目的是学习纳什平衡（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的遗憾，从而明确说明了差异数量的作用，这可能具有独立的利益。

随机游戏的学习可以说是多功能钢筋学习（MARL）中最标准和最基本的环境。在本文中，我们考虑在非渐近制度的随机游戏中分散的Marl。特别是，我们在大量的一般总和随机游戏（SGS）中建立了完全分散的Q学习算法的有限样本复杂性 - 弱循环SGS，包括对所有代理商的普通合作MARL设置具有相同的奖励（马尔可夫团队问题是一个特例。我们专注于实用的同时具有挑战性地设置完全分散的Marl，既不奖励也没有其他药剂的作用，每个试剂都可以观察到。事实上，每个特工都完全忘记了其他决策者的存在。表格和线性函数近似情况都已考虑。在表格设置中，我们分析了分散的Q学习算法的样本复杂性，以收敛到马尔可夫完美均衡（NASH均衡）。利用线性函数近似，结果用于收敛到线性近似平衡 - 我们提出的均衡的新概念 - 这描述了每个代理的策略是线性空间内的最佳回复（到其他代理）。还提供了数值实验，用于展示结果。

我们考虑在具有非线性函数近似的两名玩家零和马尔可夫游戏中学习NASH平衡，其中动作值函数通过繁殖内核Hilbert Space（RKHS）中的函数近似。关键挑战是如何在高维函数空间中进行探索。我们提出了一种新颖的在线学习算法，以最大程度地减少双重性差距来找到NASH平衡。我们算法的核心是基于不确定性的乐观原理得出的上和下置信度界限。我们证明，在非常温和的假设上，我们的算法能够获得$ O（\ sqrt {t}）$遗憾，并在对奖励功能和马尔可夫游戏的基本动态下进行多项式计算复杂性。我们还提出了我们的算法的几个扩展，包括具有伯恩斯坦型奖励的算法，可以实现更严格的遗憾，以及用于模型错误指定的另一种算法，可以应用于神经功能近似。

零和游戏中的理想策略不仅应授予玩家的平均奖励，不少于NASH均衡的价值，而且还应在次优时利用（自适应）对手。尽管马尔可夫游戏中的大多数现有作品都专注于以前的目标，但我们是否可以同时实现这两个目标仍然开放。为了解决这个问题，这项工作在马尔可夫游戏中与对抗对手进行了无重组学习，当时与事后最佳的固定政策竞争时。沿着这个方向，我们提出了一组新的正面和负面结果：当每个情节结束时对手的政策被揭示时，我们提出了实现$ \ sqrt {k} $的新的有效算法 - 遗憾的是（遗憾的是） 1）基线政策类别很小或（2）对手的政策类别很小。当两种条件不正确时，这与指数下限相辅相成。当未揭示对手的政策时，即使在最有利的情况下，当两者都是正确的情况下，我们也会证明统计硬度结果。我们的硬度结果比仅涉及计算硬度或需要进一步限制算法的现有硬度结果要强得多。

尽管固定环境中的单一机构政策优化最近在增强学习社区中引起了很多研究的关注，但是当在潜在竞争性的环境中有多个代理商在玩耍时，从理论上讲，少得多。我们通过提出和分析具有结构化但未知过渡的零和Markov游戏的新的虚拟游戏策略优化算法来向前迈进。我们考虑两类的过渡结构：分类的独立过渡和单个控制器过渡。对于这两种情况，我们都证明了紧密的$ \ widetilde {\ Mathcal {o}}（\ sqrt {k}）$遗憾的范围在$ k $ eviepodes之后，在两种代理竞争的游戏场景中。每个代理人的遗憾是针对潜在的对抗对手的衡量，他们在观察完整的政策序列后可以在事后选择一个最佳政策。我们的算法在非平稳环境中同时进行政策优化的范围下，具有上置信度结合（UCB）的乐观和虚拟游戏的结合。当两个玩家都采用所提出的算法时，他们的总体最优差距为$ \ widetilde {\ Mathcal {o}}（\ sqrt {k}）$。

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

经济学和政策等现实世界应用程序往往涉及解决多智能运动游戏与两个独特的特点：（1）代理人本质上是不对称的，并分成领导和追随者; （2）代理商有不同的奖励功能，因此游戏是普通的。该领域的大多数现有结果侧重于对称解决方案概念（例如纳什均衡）或零和游戏。它仍然开放了如何学习Stackelberg均衡 - 从嘈杂的样本有效地纳入均衡的不对称模拟 - 纳入均衡。本文启动了对Birtit反馈设置中Stackelberg均衡的样本高效学习的理论研究，我们只观察奖励的噪音。我们考虑三个代表双人普通和游戏：强盗游戏，强盗加固学习（Bandit-RL）游戏和线性匪徒游戏。在所有这些游戏中，我们使用有义的许多噪声样本来确定Stackelberg均衡和其估计版本的确切值之间的基本差距，无论算法如何，都无法封闭信息。然后，我们在对上面识别的差距最佳的基础上的数据高效学习的样本高效学习的敏锐积极结果，在依赖于依赖性的差距，误差容限和动作空间的大小，匹配下限。总体而言，我们的结果在嘈杂的强盗反馈下学习Stackelberg均衡的独特挑战，我们希望能够在未来的研究中阐明这一主题。

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

我们研究数据集假设允许求解离线双人零和Markov游戏。在与离线单代理马尔可夫决策过程的鲜明对比中，我们表明单一策略浓度假设不足以在离线双球零和马尔可夫游戏中学习纳什均衡（NE）战略。另一方面，我们提出了一个名为单侧浓度的新假设，并设计了一种悲观型算法，可在此假设下提供有效的。此外，我们表明单方面浓度假设是学习网元策略所必需的。此外，我们的算法可以实现Minimax样本复杂性，而对于两个广泛研究的设置，可以进行任何修改：数据集具有均匀浓度假设和基于转向的马尔可夫游戏。我们的工作是了解离线多智能经纪增强学习的重要初步步骤。

由于信息不对称，多智能经纪增强学习（Marl）问题是挑战。为了克服这一挑战，现有方法通常需要代理商之间的高度协调或沟通。我们考虑具有在应用中产生的分层信息结构的两个代理多武装匪徒（MAB）和MARKOV决策过程（MDP），我们利用不需要协调或通信的更简单和更高效的算法。在结构中，在每个步骤中，“领导者”首先选择她的行动，然后“追随者”在观察领导者的行动后，“追随者”决定他的行动。这两个代理观察了相同的奖励（以及MDP设置中的相同状态转换），这取决于其联合行动。对于强盗设置，我们提出了一种分层匪盗算法，实现了$ \ widetilde {\ mathcal {o}}（\ sqrt {abt}）$和近最佳差距依赖的近乎最佳的差距遗憾$ \ mathcal {o}（\ log（t））$，其中$ a $和$ b $分别是领导者和追随者的行动数，$ t $是步数。我们进一步延伸到多个追随者的情况，并且具有深层层次结构的情况，在那里我们都获得了近乎最佳的遗憾范围。对于MDP设置，我们获得$ \ widetilde {\ mathcal {o}}（\ sqrt {h ^ 7s ^ 2abt}）$后悔，其中$ h $是每集的步骤数，$ s $是数量各国，$ T $是剧集的数量。这与$ a，b $和$ t $的现有下限匹配。

在大约正确的（PAC）强化学习（RL）中，需要代理来识别具有$ 1- \ delta $的$ \ epsilon $最佳政策。尽管此问题存在最小值最佳算法，但其实例依赖性复杂性在情节马尔可夫决策过程（MDPS）中仍然难以捉摸。在本文中，我们提出了具有有限状态和动作空间的确定性情节MDP中PAC RL样品复杂性的第一个（几乎）匹配的上限和下限。特别是，我们的界限为国家行动对的新概念构成了我们称为确定性返回差距的新概念。尽管我们的依赖实例的下限是作为线性程序编写的，但我们的算法非常简单，并且在学习过程中不需要解决这样的优化问题。他们的设计和分析采用了新颖的想法，包括图理论概念，例如最小流量和最大削减，我们认为这为这个问题提供了新的启示。

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

Offline reinforcement learning (RL) concerns pursuing an optimal policy for sequential decision-making from a pre-collected dataset, without further interaction with the environment. Recent theoretical progress has focused on developing sample-efficient offline RL algorithms with various relaxed assumptions on data coverage and function approximators, especially to handle the case with excessively large state-action spaces. Among them, the framework based on the linear-programming (LP) reformulation of Markov decision processes has shown promise: it enables sample-efficient offline RL with function approximation, under only partial data coverage and realizability assumptions on the function classes, with favorable computational tractability. In this work, we revisit the LP framework for offline RL, and advance the existing results in several aspects, relaxing certain assumptions and achieving optimal statistical rates in terms of sample size. Our key enabler is to introduce proper constraints in the reformulation, instead of using any regularization as in the literature, sometimes also with careful choices of the function classes and initial state distributions. We hope our insights further advocate the study of the LP framework, as well as the induced primal-dual minimax optimization, in offline RL.

我们考虑非平稳马尔可夫决策过程中的无模型增强学习（RL）。只要其累积变化不超过某些变化预算，奖励功能和国家过渡功能都可以随时间随时间变化。我们提出了重新启动的Q学习，以上置信度范围（RestartQ-UCB），这是第一个用于非平稳RL的无模型算法，并表明它在动态遗憾方面优于现有的解决方案。具体而言，带有freedman型奖励项的restartq-ucb实现了$ \ widetilde {o}（s^{\ frac {1} {3}} {\ frac {\ frac {1} {1} {3}} {3}} {3}} {3}} {3}} {3}} {3}} {3}} {\ delta ^{\ frac {1} {3}} h t^{\ frac {2} {3}}} $，其中$ s $和$ a $分别是$ \ delta> 0 $的状态和动作的数字是变化预算，$ h $是每集的时间步数，而$ t $是时间步长的总数。我们进一步提出了一种名为Double-Restart Q-UCB的无参数算法，该算法不需要事先了解变化预算。我们证明我们的算法是\ emph {几乎是最佳}，通过建立$ \ omega的信息理论下限（s^{\ frac {1} {1} {3}}} a^{\ frac {1} {1} {3}}}}}} \ delta^{\ frac {1} {3}} h^{\ frac {2} {3}}}} t^{\ frac {2} {3}}} $，是非稳态RL中的第一个下下限。数值实验可以根据累积奖励和计算效率来验证RISTARTQ-UCB的优势。我们在相关产品的多代理RL和库存控制的示例中证明了我们的结果的力量。