本文的目的是研究线性随机迭代算法和时间差（TD）学习的控制理论分析。TD-Learning是一种线性随机迭代算法，用于估计Markov决策过程的给定策略的价值函数，这是最受欢迎和最基本的强化学习算法之一。虽然在TD学习的理论分析中有一系列成功的作品，但直到最近，研究人员在其统计效率上发现了一些保证。在本文中，我们提出了一种控制理论有限时间分析TD-Learning，其利用线性系统控制社区中的标准概念。因此，拟议的工作在控制理论中具有简单概念和分析工具的TD-Learning和Creefition Learning提供了额外的见解。

本文开发了一种新颖的控制理论框架，用于分析Q学习的非渐近融合。我们表明，具有恒定阶梯大小的异步Q学习的动态可以自然地作为离散时间随机仿射系统。此外，Q学习估计误差的演变是由两个更简单的动态系统的轨迹过度而低估的。基于这两个系统，我们在使用常量步骤时，我们推出了异步Q-Learse的新的有限时间误差。我们的分析还阐明了Q-Learning的高估现象。我们进一步说明并通过数值模拟来验证分析。

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

萨顿（Sutton），szepesv \'{a} ri和maei引入了与线性函数近似和非政策训练兼容的第一个梯度时间差异（GTD）学习算法。本文的目的是（a）提出一些具有广泛比较分析的GTD的变体，以及（b）为GTD建立新的理论分析框架。这些变体基于GTD的凸 - 孔符号鞍点解释，该解释有效地将所有GTD统一为单个框架，并基于对原始偶型梯度动力学的最新结果提供简单的稳定性分析。最后，给出了数值比较分析以评估这些方法。

受欢迎的LSPE（$ \ lambda $）策略评估算法被重新审视，以导出从一段时间内提供高概率性能保证的浓度。

在这项工作中，我们研究了解决强化学习问题的基于政策的方法，其中采用了非政策性采样和线性函数近似进行政策评估，以及包括自然政策梯度（NPG）在内的各种政策更新规则，用于政策更新。为了在致命三合会的存在下解决政策评估子问题，我们提出了一个通用算法的多步型TD学习框架，具有广义的重要性抽样比率，其中包括两个特定的算法：$ \ lambda $ Q Q $ Q Q $ - 跟踪和双面$ Q $ - 跟踪。通用算法是单个时间尺度，具有可证明的有限样本保证，并克服了非政策学习中的高方差问题。至于策略更新，我们仅使用Bellman操作员的收缩属性和单调性属性提供通用分析，以在各种策略更新规则下建立几何融合。重要的是，通过将NPG视为实施政策迭代的近似方法，我们在不引入正则化的情况下建立了NPG的几何融合，并且不使用现有文献中的镜像下降类型的分析类型。将策略更新的几何融合与策略评估的有限样本分析相结合，我们首次建立了整​​体$ \ Mathcal {o}（\ Epsilon^{ - 2}）$样本复杂性以找到最佳策略（最多达到函数近似误差）使用基于策略的方法和线性函数近似下的基于策略的方法。

强调时间差异（ETD）学习（Sutton et al。，2016）是一种成功的方法，可以通过功能近似进行政体值函数评估。尽管已显示ETD渐近地收敛到理想的值函数，但众所周知，ETD通常会遇到较大的方差，因此其样品复杂性可以随迭代次数的数量而迅速地增加。在这项工作中，我们提出了一种新的ETD方法，称为per-eTD（即定期重新启动-ETD），该方法仅在评估参数的每个迭代中重新启动和更新后续跟踪。此外，Per-ETD的设计是重新启动时期的对数增加的设计与迭代次数的数量，这确保了差异和偏见之间的最佳折衷，并使均消失了。我们表明，每个ETD收敛到与ETD相同的理想固定点，但提高了ETD的指数样品复杂性为多项式。我们的实验验证了Per-ETD的出色性能及其优于ETD的优势。

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

In large-scale machine learning, recent works have studied the effects of compressing gradients in stochastic optimization in order to alleviate the communication bottleneck. These works have collectively revealed that stochastic gradient descent (SGD) is robust to structured perturbations such as quantization, sparsification, and delays. Perhaps surprisingly, despite the surge of interest in large-scale, multi-agent reinforcement learning, almost nothing is known about the analogous question: Are common reinforcement learning (RL) algorithms also robust to similar perturbations? In this paper, we investigate this question by studying a variant of the classical temporal difference (TD) learning algorithm with a perturbed update direction, where a general compression operator is used to model the perturbation. Our main technical contribution is to show that compressed TD algorithms, coupled with an error-feedback mechanism used widely in optimization, exhibit the same non-asymptotic theoretical guarantees as their SGD counterparts. We then extend our results significantly to nonlinear stochastic approximation algorithms and multi-agent settings. In particular, we prove that for multi-agent TD learning, one can achieve linear convergence speedups in the number of agents while communicating just $\tilde{O}(1)$ bits per agent at each time step. Our work is the first to provide finite-time results in RL that account for general compression operators and error-feedback in tandem with linear function approximation and Markovian sampling. Our analysis hinges on studying the drift of a novel Lyapunov function that captures the dynamics of a memory variable introduced by error feedback.

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

学习来自数据样本的给定策略的价值函数是强化学习中的重要问题。TD（$ \ lambda $）是一个流行的算法，可以解决这个问题。但是，分配给不同$ n $ -step的权重在参数$ \ lambda $控制的TD（$ \ lambda $）中返回，随着$ n $的增加，呈指数级增长。在本文中，我们展示了一个$ \ lambda $ -schedule程序，将TD（$ \ lambda $）算法概括为参数$ \ lambda $的情况随时间步骤而异。这允许通过选择序列$ \ {\ lambda_t \} $ \ {t \ geq 1} $来指定重量分配中的灵活性，即，用户可以指定分配给不同$ n $ -step返回的权重。基于此过程，我们提出了一个on-police算法 - TD（$ \ lambda $） - 计划和两个offoly almorithms - gtd（$ \ lambda $） - 计划和tdc（$ \ lambda $） - 计划，分别。我们提供了一般马尔可夫噪声框架下所有三种算法的几乎肯定融合的证据。

我们研究了线性函数近似的政策评估问题，并且目前具有强烈的最优性保证的高效实用算法。我们首先通过证明在这个问题中建立基线的下限来建立基线和随机错误。特别是，我们在与转换内核的静止分布相关联的实例相关规范中证明了Oracle复杂性下限，并使用本地渐近最低限度机械在随机误差中证明依赖于随机误差的实例相关的下限IID观察模型。现有算法未能匹配这些下限中的至少一个：为了说明，我们分析了时间差异学习的方差减少变体，特别是它未能实现Oracle复杂性下限。为了解决这个问题，我们开发了加速，方差减少的快速时间差算法（VRFTD），其同时匹配两个下限，并达到实例 - 最优性的强烈概念。最后，我们将VRFTD算法扩展到Markovian观察的设置，并提供与I.I.D中的实例相关的收敛结果。设置到与链条的混合时间成比例的乘法因子。我们的理论保证最佳的最佳保证是通过数值实验证实的。

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.

本文考虑由马尔可夫噪声和一般共识型交互驱动的新型多代理线性随机近似算法，其中每个代理根据其本地随机近似过程演变，这取决于其邻居的信息。代理中的互连结构由时变的指向图描述。虽然已经研究了代理中的互连（至少在期望）中描述了基于协商的随机近似算法的收敛性，但是当互连矩阵简单地是随机时的情况，较少是已知的。对于任何相关的相互作用矩阵是随机的均匀强连接的图形序列，纸张导出平均误差上的有限时间界限，定义为算法从相关常微分方程的独特平衡点偏差。对于互连矩阵是随机的互连矩阵的情况，平衡点可以是在没有通信的情况下所有代理的局部均衡的任何未指明的凸起组合。考虑具有恒定和时差阶梯尺寸的情况。在需要凸起组合的情况下，任何对相邻代理之间的直平均值和相互作用可以是单向的，因此纸张不能以分布式方式实现双随机矩阵，提出了一种推挽和型分布式随机近似算法，通过利用随机矩阵的共识型算法利用分析和发展推送算法的新颖性，为时变梯度尺寸案例提供了其有限时间绑定。

随机近似算法是一种广泛使用的概率方法，用于查找矢量值构造的零，仅当函数的嘈杂测量值可用时。在迄今为止的文献中，可以区分“同步”更新，从而每次更新当前猜测的每个组件，以及'“同步”更新，从而更新一个组件。原则上，也可以在每次瞬间更新一些但不是全部的$ \ theta_t $的组件，这些组件可能被称为“批处理异步随机近似”（BASA）。另外，还可以在使用“本地”时钟与“全局”时钟之间有所区别。在本文中，我们提出了一种统一的配方异步随机近似（BASA）算法，并开发了一种通用方法，以证明这种算法会融合，而与使用是否使用了全球或本地时钟。这些融合证明利用了比现有结果较弱的假设。例如：当使用本地时钟时，现有的收敛证明要求测量噪声是I.I.D序列。在这里，假定测量误差形成了martingale差异序列。同样，迄今为止的所有结果都假设随机步骤大小满足了罗宾斯 - 单月条件的概率类似物。我们通过基础马尔可夫流程的不可约性的纯粹确定性条件代替了这一点。作为加固学习的特定应用，我们介绍了时间差算法$ td（0）$的``批次''版本，以进行价值迭代，以及$ q $ - 学习算法，以查找最佳操作值函数，还允许使用本地时钟而不是全局时钟。在所有情况下，我们在温和的条件下都比现有文献建立了这些算法的融合。

在本文中，我们建立了双Q学习和Q学习的渐近于点误差之间的理论比较。我们的结果基于基于Lyapunov方程的线性随机近似的分析，并适用于表格设置和线性函数近似，但前提是最佳策略是唯一的，并且算法收敛。我们表明，如果双Q学习使用Q学习率的两倍，并输出了两个估计量的平均值，则双Q学习的渐近于点误差完全等于Q学习的误差。我们还使用模拟给出了这种理论观察的一些实际含义。

我们研究了多智能经纪增强学习的政策评估问题，其中一组代理商，共同观察到的国家和私人本地行动和奖励，协作，以通过连接的无向网络通过本地计算和通信学习给定策略的价值函数。各种大型多种代理系统中出现此问题，包括电网，智能交通系统，无线传感器网络和多代理机器人。当状态动作空间的尺寸大时，广泛使用具有线性函数近似的时间差异学习。在本文中，我们开发了一种新的分布式时间差异学习算法，量化其有限时间性能。我们的算法将分布式随机原始方法与基于同型的方法进行了自适应调整学习率的方法，以便通过从因果导轨轨迹中采用新鲜的在线样本来最小化平均投影的Bellman误差。我们明确考虑了采样的Markovian性质，并改善了从$ O（1 / \ sqrt {t}）$到〜$ o（1 / t）$的最佳已知的有限时间误差，其中$ t $迭代的总数。

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

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

我们研究了随机近似程序，以便基于观察来自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 $的值）。