最大化马尔可夫和固定的累积奖励函数，即在国家行动对和时间独立于时间上定义，足以在马尔可夫决策过程（MDP）中捕获多种目标。但是，并非所有目标都可以以这种方式捕获。在本文中，我们研究了凸MDP，其中目标表示为固定分布的凸功能，并表明它们不能使用固定奖励函数进行配制。凸MDP将标准加强学习（RL）问题提出概括为一个更大的框架，其中包括许多受监督和无监督的RL问题，例如学徒学习，约束MDP和所谓的“纯探索”。我们的方法是使用Fenchel二重性将凸MDP问题重新将凸MDP问题重新制定为涉及政策和成本（负奖励）的最小游戏。我们提出了一个用于解决此问题的元偏金属，并表明它统一了文献中许多现有的算法。

在学徒学习（AL）中，我们在没有获得成本函数的情况下给予马尔可夫决策过程（MDP）。相反，我们观察由根据某些政策执行的专家采样的轨迹。目标是找到一个与专家对某些预定义的成本函数的性能相匹配的策略。我们介绍了AL的在线变体（在线学徒学习; OAL），其中代理商预计与环境相互作用，在与环境互动的同时相互表现。我们表明，通过组合两名镜面血缘无遗憾的算法可以有效地解决了OAL问题：一个用于策略优化，另一个用于学习最坏情况的成本。通过采用乐观的探索，我们使用$ O（\ SQRT {k}）$后悔派生算法，其中$ k $是与MDP的交互数量以及额外的线性错误术语，其取决于专家轨迹的数量可用的。重要的是，我们的算法避免了在每次迭代时求解MDP的需要，与先前的AL方法相比，更实用。最后，我们实现了我们算法的深层变体，该算法与Gail \ Cite {Ho2016Generative}共享了一些相似之处，但在鉴别者被替换为OAL问题的成本。我们的模拟表明OAL在高维控制问题中表现良好。

找到同一问题的不同解决方案是与创造力和对新颖情况的适应相关的智能的关键方面。在钢筋学习中，一套各种各样的政策对于勘探，转移，层次结构和鲁棒性有用。我们提出了各种各样的连续政策，一种发现在继承人功能空间中多样化的政策的方法，同时确保它们接近最佳。我们将问题形式形式化为受限制的马尔可夫决策过程（CMDP），目标是找到最大化多样性的政策，其特征在于内在的多样性奖励，同时对MDP的外在奖励保持近乎最佳。我们还分析了最近提出的稳健性和歧视奖励的绩效，并发现它们对程序的初始化敏感，并且可以收敛到次优溶液。为了缓解这一点，我们提出了新的明确多样性奖励，该奖励旨在最大限度地减少集合中策略的继承人特征之间的相关性。我们比较深度控制套件中的不同多样性机制，发现我们提出的明确多样性的类型对于发现不同的行为是重要的，例如不同的运动模式。

强化学习被广泛用于在与环境互动时需要执行顺序决策的应用中。当决策要求包括满足一些安全限制时，问题就变得更加具有挑战性。该问题在数学上是作为约束的马尔可夫决策过程（CMDP）提出的。在文献中，可以通过无模型的方式解决各种算法来解决CMDP问题，以实现$ \ epsilon $ - 最佳的累积奖励，并使用$ \ epsilon $可行的政策。 $ \ epsilon $可行的政策意味着它遭受了违规的限制。这里的一个重要问题是，我们是否可以实现$ \ epsilon $ - 最佳的累积奖励，并违反零约束。为此，我们主张使用随机原始偶对偶方法来解决CMDP问题，并提出保守的随机原始二重算法（CSPDA），该算法（CSPDA）显示出$ \ tilde {\ tilde {\ Mathcal {o}} \ left（1 /\ epsilon^2 \ right）$样本复杂性，以实现$ \ epsilon $ - 最佳累积奖励，违反零约束。在先前的工作中，$ \ epsilon $ - 最佳策略的最佳可用样本复杂性是零约束的策略是$ \ tilde {\ Mathcal {o}}} \ left（1/\ epsilon^5 \ right）$。因此，与最新技术相比，拟议的算法提供了重大改进。

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

在许多综合设置（例如视频游戏）和GO中，增强学习（RL）超出了人类的绩效。但是，端到端RL模型的现实部署不太常见，因为RL模型对环境的轻微扰动非常敏感。强大的马尔可夫决策过程（MDP）框架（其中的过渡概率属于名义模型设置的不确定性）提供了一种开发健壮模型的方法。虽然先前的分析表明，RL算法是有效的，假设访问生成模型，但尚不清楚RL在更现实的在线设置下是否可以有效，这需要在探索和开发之间取得仔细的平衡。在这项工作中，我们通过与未知的名义系统进行互动来考虑在线强大的MDP。我们提出了一种强大的乐观策略优化算法，该算法可有效。为了解决由对抗性环境引起的其他不确定性，我们的模型具有通过Fenchel Conjugates得出的新的乐观更新规则。我们的分析确定了在线强大MDP的第一个遗憾。

在线强化学习（RL）中的挑战之一是代理人需要促进对环境的探索和对样品的利用来优化其行为。无论我们是否优化遗憾，采样复杂性，状态空间覆盖范围或模型估计，我们都需要攻击不同的勘探开发权衡。在本文中，我们建议在分离方法组成的探索 - 剥削问题：1）“客观特定”算法（自适应）规定哪些样本以收集到哪些状态，似乎它可以访问a生成模型（即环境的模拟器）; 2）负责尽可能快地生成规定样品的“客观无关的”样品收集勘探策略。建立最近在随机最短路径问题中进行探索的方法，我们首先提供一种算法，它给出了每个状态动作对所需的样本$ B（S，a）$的样本数量，需要$ \ tilde {o} （bd + d ^ {3/2} s ^ 2 a）收集$ b = \ sum_ {s，a} b（s，a）$所需样本的$时间步骤，以$ s $各国，$ a $行动和直径$ d $。然后我们展示了这种通用探索算法如何与“客观特定的”策略配对，这些策略规定了解决各种设置的样本要求 - 例如，模型估计，稀疏奖励发现，无需无成本勘探沟通MDP - 我们获得改进或新颖的样本复杂性保证。

强化学习理论集中在两个基本问题上：实现低遗憾，并确定$ \ epsilon $ - 最佳政策。虽然简单的减少允许人们应用低温算法来获得$ \ epsilon $ - 最佳政策并达到最坏的最佳速率，但尚不清楚低regret算法是否可以获得实例 - 最佳率的策略识别率。我们表明这是不可能的 - 在遗憾和确定$ \ epsilon $ - 最佳政策之间以最佳的利率确定了基本的权衡。由于我们的负面发现，我们提出了针对PAC表格增强学习实例依赖性样本复杂性的新量度，该方法明确说明了基础MDP中可达到的国家访问分布。然后，我们提出和分析一种基于计划的新型算法，该算法达到了这种样本的复杂性 - 产生的复杂性会随着次要差距和状态的“可达到性”而缩放。我们显示我们的算法几乎是最小的最佳选择，并且在一些示例中，我们实例依赖性样品复杂性比最差案例界限可显着改善。

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

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

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

Robust Markov decision processes (RMDPs) are promising models that provide reliable policies under ambiguities in model parameters. As opposed to nominal Markov decision processes (MDPs), however, the state-of-the-art solution methods for RMDPs are limited to value-based methods, such as value iteration and policy iteration. This paper proposes Double-Loop Robust Policy Gradient (DRPG), the first generic policy gradient method for RMDPs with a global convergence guarantee in tabular problems. Unlike value-based methods, DRPG does not rely on dynamic programming techniques. In particular, the inner-loop robust policy evaluation problem is solved via projected gradient descent. Finally, our experimental results demonstrate the performance of our algorithm and verify our theoretical guarantees.

我们介绍了表演性强化学习的框架，学习者选择的政策会影响环境的基本奖励和过渡动态。遵循有关表演预测的最新文献〜\ cite {perdomo等。 Al。，2020}，我们介绍了性能稳定政策的概念。然后，我们考虑了强化学习问题的正则版本，并表明，在合理的假设对过渡动态的合理假设下，反复优化此目标将其收敛到性能稳定的策略。我们的证明利用了强化学习问题的双重观点，并且可能在分析其他算法与决策依赖性环境的融合方面具有独立的兴趣。然后，我们将结果扩展到学习者仅执行梯度上升步骤而不是完全优化目标的设置，以及学习者可以从变化的环境中访问有限数量的轨迹的设置。对于这两种设置，我们都利用表演性增强学习的双重表述，并建立与稳定解决方案的融合。最后，通过对网格世界环境的广泛实验，我们证明了收敛对各种参数的依赖性，例如正则化，平滑度和样品数量。

尽管在理解增强学习的最小样本复杂性（RL）（在“最坏情况”的实例上学习的复杂性）方面已经取得了很多进展，但这种复杂性的衡量标准通常不会捕捉到真正的学习困难。在实践中，在“简单”的情况下，我们可能希望获得比最糟糕的实例可以实现的要好得多。在这项工作中，我们试图理解在具有线性函数近似的RL设置中学习近乎最佳策略（PAC RL）的“实例依赖性”复杂性。我们提出了一种算法，\ textsc {pedel}，该算法实现了依赖于实例的复杂性的量度，这是RL中的第一个具有功能近似设置，从而捕获了每个特定问题实例的学习难度。通过一个明确的示例，我们表明\ textsc {pedel}可以在低重晶，最小值 - 最佳算法上获得可证明的收益，并且这种算法无法达到实例 - 最佳速率。我们的方法取决于基于设计的新型实验程序，该程序将勘探预算重点放在与学习近乎最佳政策最相关的“方向”上，并且可能具有独立的兴趣。

我们考虑了具有未知成本函数的大规模马尔可夫决策过程，并解决了从有限一套专家演示学习政策的问题。我们假设学习者不允许与专家互动，并且无法访问任何类型的加固信号。现有的逆钢筋学习方法具有强大的理论保证，但在计算上是昂贵的，而最先进的政策优化算法实现了重大的经验成功，但受到有限的理论理解受到阻碍。为了弥合理论与实践之间的差距，我们使用拉格朗日二元介绍了一种新的Bilinear鞍点框架。所提出的原始双视点允许我们通过随机凸优化的镜头开发出无模型可释放的算法。该方法享有实现，低内存要求和独立于州数量的计算和采样复杂性的优点。我们进一步提出了同等的无悔在线学习解释。

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

与表征解决马尔可夫决策过程（MDP）样品复杂性的进步相反，解决约束MDP（CMDP）的最佳统计复杂性仍然未知。我们通过在折扣CMDP中学习近乎最佳策略的样本复杂性上的最小上限和下限来解决这个问题，并访问生成模型（模拟器）。特别是，我们设计了一种基于模型的算法，该算法解决了两个设置：（i）允许违反小小的约束的可行性，以及（ii）严格的可行性，其中需要输出策略来满足约束。对于（i），我们证明我们的算法通过制作$ \ tilde {o} \ left（\ frac {s a \ log（1/\ delta）来返回带有概率$ 1- \ delta $的$ \ epsilon $ - 优势策略} {（1- \ gamma）^3 \ epsilon^2} \ right）$ QUERIES $ QUERIES与生成模型相匹配，因此与无约束的MDP的样品复杂性匹配。对于（ii），我们表明该算法的样本复杂性是由$ \ tilde {o} \ left（\ frac {s a a \ log，\ log（1/\ delta）} {（1 - \ gamma）^5 \，\ epsilon^2 \ zeta^2} \ right）$，其中$ \ zeta $是与问题相关的slater常数，其特征是可行区域的大小。最后，我们证明了严格的可行性设置的匹配较低限制，因此获得了折扣CMDP的第一个最小值最佳界限。我们的结果表明，在允许违反小小的约束时，学习CMDP与MDP一样容易，但是当我们要求零约束违规时，本质上更加困难。

我们介绍了一种普遍的策略，可实现有效的多目标勘探。它依赖于adagoal，一种基于简单约束优化问题的新的目标选择方案，其自适应地针对目标状态，这既不是太困难也不是根据代理目前的知识达到的。我们展示了Adagoal如何用于解决学习$ \ epsilon $ -optimal的目标条件的政策，以便在$ L $ S_0 $ S_0 $奖励中获得的每一个目标状态，以便在$ S_0 $中获取。免费马尔可夫决策过程。在标准的表格外壳中，我们的算法需要$ \ tilde {o}（l ^ 3 s a \ epsilon ^ { - 2}）$探索步骤，这几乎很少最佳。我们还容易在线性混合Markov决策过程中实例化Adagoal，其产生具有线性函数近似的第一目标导向的PAC保证。除了强大的理论保证之外，迈克纳队以现有方法的高级别算法结构为锚定，为目标条件的深度加固学习。

离线增强学习（RL）的样本效率保证通常依赖于对功能类别（例如Bellman-Completeness）和数据覆盖范围（例如，全政策浓缩性）的强有力的假设。尽管最近在放松这些假设方面做出了努力，但现有作品只能放松这两个因素之一，从而使另一个因素的强烈假设完好无损。作为一个重要的开放问题，我们是否可以实现对这两个因素的假设较弱的样本效率离线RL？在本文中，我们以积极的态度回答了这个问题。我们基于MDP的原始偶对偶进行分析了一种简单的算法，其中双重变量（打折占用）是使用密度比函数对离线数据进行建模的。通过适当的正则化，我们表明该算法仅在可变性和单极浓缩性下具有多项式样品的复杂性。我们还基于不同的假设提供了替代分析，以阐明离线RL原始二算法的性质。

我们研究了平均奖励马尔可夫决策过程（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。我们的理论优势通过数值实验来证实。