直接政策搜索作为现代强化学习（RL）的工作人员之一，其在连续控制任务中的应用最近引起了不断的关注。在这项工作中，我们研究了用于学习线性风险敏感和鲁棒控制器的政策梯度（PG）方法的收敛理论。特别地，我们开发PG方法，可以通过采样系统轨迹以无衍生方式实现，并建立全球收敛性和样本复杂性，这导致风险敏感和强大控制中的两个基本环境的解决方案：有限地平线线性指数二次高斯，以及有限地平线线性二次干扰衰减问题。作为副产品，我们的结果还为解决零和线性二次动态游戏的PG方法的全局融合提供了第一种样本复杂性，这是一种非透明的极限优化问题，该问题用作多功能钢筋中的基线设置学习（Marl）与连续空间。我们的算法的一个特征是在学习阶段，保留了一定程度的控制器的鲁棒性/风险敏感性，因此我们被称为隐式正则化属性，并且是安全关键控制系统的基本要求。

我们考虑使用有限的地平线上具有随机动力学的通用N-N-玩家线性季度游戏，并证明了自然策略梯度方法与NASH平衡的全球收敛性。为了证明该方法的收敛性，我们需要系统中有一定数量的噪声。我们给出了一个条件，基本上是在模型参数方面对噪声的协方差的下限，以确保收敛。我们通过数值实验说明了我们的结果，以表明即使在策略梯度方法可能不会在确定性设置中收敛的情况下，噪声的添加也会导致收敛。

我们研究了在两人零和马尔可夫游戏中找到NASH平衡的问题。由于其作为最小值优化程序的表述，解决该问题的自然方法是以交替的方式对每个玩家进行梯度下降/上升。但是，由于基本目标函数的非跨性别/非障碍性，该方法的理论理解是有限的。在我们的论文中，我们考虑解决马尔可夫游戏的熵登记变体。正则化将结构引入了优化景观中，从而使解决方案更加可识别，并允许更有效地解决问题。我们的主要贡献是表明，在正则化参数的正确选择下，梯度下降算法会收敛到原始未注册问题的NASH平衡。我们明确表征了我们算法的最后一个迭代的有限时间性能，该算法的梯度下降上升算法的现有收敛界限大大改善了而没有正则化。最后，我们通过数值模拟来补充分析，以说明算法的加速收敛性。

策略梯度方法适用于复杂的，不理解的，通过对参数化的策略进行随机梯度下降来控制问题。不幸的是，即使对于可以通过标准动态编程技术解决的简单控制问题，策略梯度算法也会面临非凸优化问题，并且被广泛理解为仅收敛到固定点。这项工作确定了结构属性 - 通过几个经典控制问题共享 - 确保策略梯度目标函数尽管是非凸面，但没有次优的固定点。当这些条件得到加强时，该目标满足了产生收敛速率的Polyak-lojasiewicz（梯度优势）条件。当其中一些条件放松时，我们还可以在任何固定点的最佳差距上提供界限。

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

本文分析了双模的彼此优化随机算法框架。 Bilevel优化是一类表现出两级结构的问题，其目标是使具有变量的外目标函数最小化，该变量被限制为对（内部）优化问题的最佳解决方案。我们考虑内部问题的情况是不受约束的并且强烈凸起的情况，而外部问题受到约束并具有平滑的目标函数。我们提出了一种用于解决如此偏纤维问题的两次时间尺度随机近似（TTSA）算法。在算法中，使用较大步长的随机梯度更新用于内部问题，而具有较小步长的投影随机梯度更新用于外部问题。我们在各种设置下分析了TTSA算法的收敛速率：当外部问题强烈凸起（RESP。〜弱凸）时，TTSA算法查找$ \ MATHCAL {O}（k ^ { - 2/3}）$ -Optimal（resp。〜$ \ mathcal {o}（k ^ {-2/5}）$ - 静止）解决方案，其中$ k $是总迭代号。作为一个应用程序，我们表明，两个时间尺度的自然演员 - 批评批评近端策略优化算法可以被视为我们的TTSA框架的特殊情况。重要的是，与全球最优政策相比，自然演员批评算法显示以预期折扣奖励的差距，以$ \ mathcal {o}（k ^ { - 1/4}）的速率收敛。

We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. Focusing on a stochastic query model that provides noisy evaluations of the operator, we analyze a variance-reduced stochastic approximation scheme, and establish non-asymptotic bounds for both the operator defect and the estimation error, measured in an arbitrary semi-norm. In contrast to worst-case guarantees, our bounds are instance-dependent, and achieve the local asymptotic minimax risk non-asymptotically. For linear operators, contractivity can be relaxed to multi-step contractivity, so that the theory can be applied to problems like average reward policy evaluation problem in reinforcement learning. We illustrate the theory via applications to stochastic shortest path problems, two-player zero-sum Markov games, as well as policy evaluation and $Q$-learning for tabular Markov decision processes.

In many sequential decision-making problems one is interested in minimizing an expected cumulative cost while taking into account risk, i.e., increased awareness of events of small probability and high consequences. Accordingly, the objective of this paper is to present efficient reinforcement learning algorithms for risk-constrained Markov decision processes (MDPs), where risk is represented via a chance constraint or a constraint on the conditional value-at-risk (CVaR) of the cumulative cost. We collectively refer to such problems as percentile risk-constrained MDPs. Specifically, we first derive a formula for computing the gradient of the Lagrangian function for percentile riskconstrained MDPs. Then, we devise policy gradient and actor-critic algorithms that (1) estimate such gradient, (2) update the policy in the descent direction, and (3) update the Lagrange multiplier in the ascent direction. For these algorithms we prove convergence to locally optimal policies. Finally, we demonstrate the effectiveness of our algorithms in an optimal stopping problem and an online marketing application.

参与者 - 批评（AC）增强学习算法一直是许多具有挑战性的应用背后的强大力量。然而，它的收敛性一般都是脆弱的。为了研究其不稳定性，现有作品主要考虑具有有限状态和动作空间的罕见的双环变体或基本模型。我们研究了更实用的单样本两次尺度AC，用于解决规范线性二次调节器（LQR）问题，其中演员和评论家在每个迭代中仅在无界的连续状态和动作空间中使用单个迭代中的单个样本更新一次。现有的分析无法得出这样一个具有挑战性的情况的融合。我们开发了一个新的分析框架，该框架允许建立全局收敛到$ \ epsilon $ -optimal解决方案，最多最多是$ \ tilde {\ Mathcal {o}}}（\ epsilon^{ - 2.5}）$样本复杂性。据我们所知，这是单个样本两次尺度AC的第一个有限时间收敛分析，用于以全球最优性求解LQR。样本复杂性通过订单改善了其他变体的复杂性，从而阐明了单个样品算法的实际智慧。我们还通过全面的模拟比较进一步验证了理论发现。

我们研究了随机近似程序，以便基于观察来自ergodic Markov链的长度$ n $的轨迹来求近求解$ d -dimension的线性固定点方程。我们首先表现出$ t _ {\ mathrm {mix}} \ tfrac {n}} \ tfrac {n}} \ tfrac {d}} \ tfrac {d} {n} $的非渐近性界限。$ t _ {\ mathrm {mix $是混合时间。然后，我们证明了一种在适当平均迭代序列上的非渐近实例依赖性，具有匹配局部渐近最小的限制的领先术语，包括对参数$的敏锐依赖（d，t _ {\ mathrm {mix}}） $以高阶术语。我们将这些上限与非渐近Minimax的下限补充，该下限是建立平均SA估计器的实例 - 最优性。我们通过Markov噪声的政策评估导出了这些结果的推导 - 覆盖了所有$ \ lambda \中的TD（$ \ lambda $）算法，以便[0,1）$ - 和线性自回归模型。我们的实例依赖性表征为HyperParameter调整的细粒度模型选择程序的设计开放了门（例如，在运行TD（$ \ Lambda $）算法时选择$ \ lambda $的值）。

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.

通过在线规范相关性分析的问题，我们提出了\ emph {随机缩放梯度下降}（SSGD）算法，以最小化通用riemannian歧管上的随机功能的期望。 SSGD概括了投影随机梯度下降的思想，允许使用缩放的随机梯度而不是随机梯度。在特殊情况下，球形约束的特殊情况，在广义特征向量问题中产生的，我们建立了$ \ sqrt {1 / t} $的令人反感的有限样本，并表明该速率最佳最佳，直至具有积极的积极因素相关参数。在渐近方面，一种新的轨迹平均争论使我们能够实现局部渐近常态，其速率与鲁普特 - Polyak-Quaditsky平均的速率匹配。我们将这些想法携带在一个在线规范相关分析，从事文献中的第一次获得了最佳的一次性尺度算法，其具有局部渐近融合到正常性的最佳一次性尺度算法。还提供了用于合成数据的规范相关分析的数值研究。

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

我们考虑解决强大的马尔可夫决策过程（MDP）的问题，该过程涉及一组折扣，有限状态，有限的动作空间MDP，具有不确定的过渡核。计划的目的是找到一项强大的政策，以优化针对过渡不确定性的最坏情况值，从而将标准MDP计划作为特殊情况。对于$（\ Mathbf {s}，\ Mathbf {a}）$ - 矩形不确定性集，我们开发了一种基于策略的一阶方法，即稳健的策略镜像下降（RPMD），并建立$ \ Mathcal {o }（\ log（1/\ epsilon））$和$ \ Mathcal {o}（1/\ epsilon）$迭代复杂性，用于查找$ \ epsilon $ -optimal策略，并带有两个增加的步骤式方案。 RPMD的先前收敛适用于任何Bregman差异，前提是政策空间在以初始政策为中心时通过差异测量的半径限制了半径。此外，当布雷格曼的分歧对应于平方的欧几里得距离时，我们建立了一个$ \ mathcal {o}（\ max \ {1/\ epsilon，1/（\ eta \ eTa \ epsilon^2）\ epsilon^2）\任何常量的步进$ \ eta $。对于Bregman差异的一般类别，如果不确定性集满足相对强的凸度，则还为RPMD建立了类似的复杂性。当仅通过与名义环境的在线互动获得一阶信息时，我们进一步开发了一个名为SRPMD的随机变体。对于Bregman General Divergences，我们建立了一个$ \ MATHCAL {O}（1/\ Epsilon^2）$和$ \ Mathcal {O}（1/\ Epsilon^3）$样品复杂性，具有两个增加的静态方案。对于Euclidean Bregman Divergence，我们建立了一个$ \ MATHCAL {O}（1/\ Epsilon^3）$样本复杂性，并具有恒定的步骤。据我们所知，所有上述结果似乎是应用于强大的MDP问题的基于策略的一阶方法的新事物。

Q学习长期以来一直是最受欢迎的强化学习算法之一，几十年来，Q学习的理论分析一直是一个活跃的研究主题。尽管对Q-学习的渐近收敛分析的研究具有悠久的传统，但非肿瘤收敛性直到最近才受到积极研究。本文的主要目的是通过控制系统的观点研究马尔可夫观察模型下异步Q学习的新有限时间分析。特别是，我们引入了Q学习的离散时间变化的开关系统模型，并减少了分析的步骤尺寸，这显着改善了使用恒定步骤尺寸的开关系统分析的最新开发，并导致\（\（\）（\） Mathcal {o} \ left（\ sqrt {\ frac {\ log k} {k}}} \ right）\）\）\）\）\）\）\）\）与大多数艺术状态相当或更好。同时，新应用了使用类似转换的技术，以避免通过减小的步骤尺寸提出的分析中的难度。提出的分析带来了其他见解，涵盖了不同的方案，并提供了新的简化模板，以通过其独特的连接与离散时间切换系统的独特联系来加深我们对Q学习的理解。

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

多功能钢筋学习已成功应用于许多挑战性问题。尽管有这些经验成功，但对不同算法的理论理解缺乏，主要是由于状态 - 行动空间的指数增长与代理人数引起的维度诅咒。我们研究了多蛋白线性二次调节剂（LQR）的基本问题，在该刻度部分可互换的情况下。在此设置中，我们开发了一个分层演员 - 批评算法，其计算复杂性独立于代理总数，并证明了其全局线性融合到最佳政策。由于LQRS经常用于近似一般动态系统，本文提供了更好地理解一般分层平均场多功能增强学习的重要一步。

这项教程调查概述了统计学习理论中最新的非征血性进步与控制和系统识别相关。尽管在所有控制领域都取得了重大进展，但在线性系统的识别和学习线性二次调节器时，该理论是最发达的，这是本手稿的重点。从理论的角度来看，这些进步的大部分劳动都在适应现代高维统计和学习理论的工具。虽然与控制对机器学习的工具感兴趣的理论家高度相关，但基础材料并不总是容易访问。为了解决这个问题，我们提供了相关材料的独立介绍，概述了基于最新结果的所有关键思想和技术机械。我们还提出了许多开放问题和未来的方向。

我们研究了马尔可夫潜在游戏（MPG）中多机构增强学习（RL）问题的策略梯度方法的全球非反应收敛属性。要学习MPG的NASH平衡，在该MPG中，状态空间的大小和/或玩家数量可能非常大，我们建议使用TANDEM所有玩家运行的新的独立政策梯度算法。当梯度评估中没有不确定性时，我们表明我们的算法找到了$ \ epsilon $ -NASH平衡，$ o（1/\ epsilon^2）$迭代复杂性并不明确取决于状态空间大小。如果没有确切的梯度，我们建立$ O（1/\ epsilon^5）$样品复杂度在潜在的无限大型状态空间中，用于利用函数近似的基于样本的算法。此外，我们确定了一类独立的政策梯度算法，这些算法都可以融合零和马尔可夫游戏和马尔可夫合作游戏，并与玩家不喜欢玩的游戏类型。最后，我们提供了计算实验来证实理论发展的优点和有效性。

梯度下降（GDA）方法是生成对抗网络（GAN）中最小值优化的主流算法。 GDA的收敛特性引起了最近文献的重大兴趣。具体而言，对于$ \ min _ {\ mathbf {x}} \ max _ {\ mathbf {y}} f（\ mathbf {x}; \ m m缩y} $以及$ \ mathbf {x} $，（lin等，2020）中的nonConvex证明了GDA的收敛性，带有sptepize的比率$ \ eta _ {\ mathbf {y}}}}/\ eta _ { }} = \ theta（\ kappa^2）$ with $ \ eta _ {\ mathbf {x}} $和$ \ eta _ {\ eta _ {\ mathbf {y}} $是$ \ mathbf {x}} $和$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ Mathbf {y} $和$ \ kappa $是$ \ mathbf {y} $的条件号。尽管该步骤大比表明对最小玩家进行缓慢的训练，但实用的GAN算法通常对两个变量采用类似的步骤，表明理论和经验结果之间存在较大差距。在本文中，我们的目标是通过分析常规\ emph {nonconvex-nonconcave} minimax问题的\ emph {local contergence}来弥合这一差距。我们证明，$ \ theta（\ kappa）$的得分比是必要且足够的，足以使GDA局部收敛到Stackelberg equilibrium，其中$ \ kappa $是$ \ mathbf {y} $的本地条件号。我们证明了与匹配的下限几乎紧密的收敛速率。我们进一步将收敛保证扩展到随机GDA和额外梯度方法（例如）。最后，我们进行了几项数值实验来支持我们的理论发现。