梯度时间差（梯度TD）算法是用于钢筋学习中的政策评估的流行随机近似（SA）算法。在这里，我们考虑具有额外的重球动量项的梯度TD算法，并提供阶梯尺寸和动量参数的选择，确保这些算法的几乎肯定偶然的趋势。在这样做时，我们将沉重的球梯度TD分解为三个单独的迭代，具有不同的步骤尺寸。我们首先使用当前文献的结果进行一次时间尺度SA设置分析这些迭代。但是，一时间时间形案例是限制性的，并且可以通过查看迭代的三次时间尺度分解来提供更一般的分析。在此过程中，我们提供了一般三次Timescale SA的稳定性和融合的第一个条件。然后，我们证明了沉重的球梯度TD算法使用我们的三个时间尺度SA分析来收敛。最后，我们在标准RL问题上评估了这些算法，并报告了Vanilla算法的性能提高。

学习来自数据样本的给定策略的价值函数是强化学习中的重要问题。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 $） - 计划，分别。我们提供了一般马尔可夫噪声框架下所有三种算法的几乎肯定融合的证据。

本文涉及由马尔可夫噪声驱动的随机近似的收敛和渐近统计：$$ \ theta_ {n + 1} = \ theta_n + \ alpha_ {n + 1} f（\ theta_n，\ phi_ {n + 1}）\， ，\ quad n \ ge 0，$$，其中每个$ \ theta_n \ in \ re ^ d $，$ \ {\ phi_n \} $是一般状态空间x上的马尔可夫链，静止分配$ \ pi $和$ f：\ re ^ d \ times \ text {x} \ to \ re ^ d $。除了在$ f $的标准lipschitz边界，以及消失的步骤大小序列$ \ {\ alpha_n \ \} $的条件外，假设相关ode是全局渐近稳定的静止点表示$ \ theta ^ * $ ，其中$ \ bar f（\ theta）= e [f（\ theta，\ phi）] $ with $ \ phi \ sim \ pi $。而且，ode @ $ \ infty $ virect with advoore字段，$$ \ bar f_ \ idty（\ theta）：= \ lim_ {r \ to \ infty} r ^ { - 1} \ bar f（r \ theta）\ ,, \ qquad \ theta \ in \ re ^ d，$$是渐近稳定的。主要贡献总结如下：（i）如果$ \ phi $是几何ergodic，则序列$ \ theta $是融合的，并且在$ f $兼容兼容的界限。剩余的结果是在马尔可夫链的更强大假设下建立：Donsker-varadhan Lyapunov漂移条件的稍微弱版本（DV3）。 （ii）为联合过程$ \ {\ theta_n，\ phi_n \} $构建Lyapunov函数，这意味着$ \ {\ theta_n \} $ in $ l_4 $的融合。 （iii）建立了功能性CLT，以及归一化误差$ z_n：=（\ theta_n- \ theta ^ *）/ \ sqrt {\ alpha_n} $的常规一维CLT。时刻界限结合了CLT暗示了归一化协方差的收敛，$$ \ lim_ {n \ to \ infty} e [z_n z_n ^ t] = \ sigma_ \ theta，$$在$ \ sigma_ \ theta $ where asbptotic协方差出现在CLT中。 （iv）提供了一个例子，其中马尔可夫链$ \ phi $是几何ergodic，但它不满足（dv3）。虽然算法收敛，但第二个时刻是无限的。

事实证明，行为政策与目标政策不同并用于获得学习经验的政策策略在强化学习中具有巨大的实践价值。但是，即使对于简单的凸问题，例如线性值函数近似，这些算法也不能保证是稳定的。为了解决这个问题，在这种情况下引入了可证明会收敛的替代算法，最著名的是梯度下降时间差异（GTD）学习。然而，这种算法和其他类似的算法往往比传统的时间差异学习更慢得多。在本文中，我们建议通过在连续参数更新中引入二阶差异来提高GTD2的梯度下降时间差异（梯度DD）学习。我们在线性值函数近似的框架中研究了该算法，理论上通过应用随机近似理论来证明其收敛性。分析显示其比GTD2的改善。通过经验研究该模型的随机步行任务，Boyan-Chain任务和Baird的非政策反例，我们发现对GTD2的实质性改善，在某些情况下，甚至比传统的TD学习更好的表现甚至更好。

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

致命的三合会是指在使用违法学习，函数逼近和同时引导时的加强学习算法的不稳定性。在本文中，我们将目标网络作为破坏致命三层的工具，为目标网络稳定训练的传统智慧提供理论支持。我们首先提出并分析了一种新的目标网络更新规则，该规则增加了两个预测的常用的Polyak平均样式更新。然后，我们将目标网络和脊正则化在几个不同的算法中应用，并显示它们对正则化TD固定点的融合。这些算法是具有线性函数近似和自动启动的禁止策略，跨越策略评估和控制，以及折扣和平均奖励设置。特别是，我们在非批评性和更改行为策略下提供第一个收敛线性$ Q $算法，没有双级优化。

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.

Q-learning and SARSA(0) with $\epsilon$-greedy exploration are leading reinforcement learning methods, and their tabular forms converge to the optimal Q-function under reasonable conditions. However, with function approximation, these methods exhibit strange behaviors, e.g., policy oscillation and chattering, convergence to different attractors (possibly even the worst policy) on different runs, etc., apart from the usual instability. Accordingly, a theory to explain these phenomena has been a long-standing open problem, even for basic linear function approximation (Sutton, 1999). Our work uses differential inclusion theory to provide the first framework for resolving this problem. We further illustrate via numerical examples how this framework helps explain these algorithms' asymptotic behaviors.

在多代理加固学习（MARL）中，多个代理商与普通环境相互作用，也与彼此相互作用，以解决连续决策中的共同问题。它在博彩，机器人，金融等中具有广泛的应用。在这项工作中，我们推导了一种在Marl中有用的分布式非线性随机近似方案的迭代对数的新规定。特别是，我们的结果描述了几乎每个样本路径上的收敛速度，其中算法会聚。这一结果是其分布式设置中的第一类，并提供比现有的更深层次的见解，它只讨论预期的收敛率或CLT感觉。重要的是，我们的结果在显着较弱的假设下保持：八卦矩阵都不需要是双随机的，也不是Spandsize Scalual。作为一个应用程序，我们表明，对于使用$ \ gamma \ In（0,1）中的步骤中的Spectize $ n ^ { - \ gamma} $，其中具有线性函数近似的分布式Td（0）算法具有$的收敛速度o（\ sqrt {n ^ { - \ gamma} \ ln n}）$ as;对于$ 1 / n $类型的步骤，同样是$ o（\ sqrt {n ^ { - 1} \ ln \ ln n}）$ a ..这些衰减率不依赖于描绘不同剂中相互作用的图表。

In this paper, we study the almost sure boundedness and the convergence of the stochastic approximation (SA) algorithm. At present, most available convergence proofs are based on the ODE method, and the almost sure boundedness of the iterations is an assumption and not a conclusion. In Borkar-Meyn (2000), it is shown that if the ODE has only one globally attractive equilibrium, then under additional assumptions, the iterations are bounded almost surely, and the SA algorithm converges to the desired solution. Our objective in the present paper is to provide an alternate proof of the above, based on martingale methods, which are simpler and less technical than those based on the ODE method. As a prelude, we prove a new sufficient condition for the global asymptotic stability of an ODE. Next we prove a ``converse'' Lyapunov theorem on the existence of a suitable Lyapunov function with a globally bounded Hessian, for a globally exponentially stable system. Both theorems are of independent interest to researchers in stability theory. Then, using these results, we provide sufficient conditions for the almost sure boundedness and the convergence of the SA algorithm. We show through examples that our theory covers some situations that are not covered by currently known results, specifically Borkar-Meyn (2000).

强化学习的最新出现为使用这些算法计算的参数估计值创造了强大的统计推断方法的需求。现有的在线学习中统计推断的方法仅限于涉及独立采样观察的设置，而现有的强化学习中统计推断方法（RL）仅限于批处理设置。在线引导程序是一种灵活，有效的方法，用于线性随机近似算法中的统计推断，但在涉及Markov噪声（例如RL）的设置中，其功效尚未探索。在本文中，我们研究了在线引导方法在RL中的统计推断的使用。特别是，我们专注于时间差异（TD）学习和梯度TD（GTD）学习算法，它们本身就是马尔可夫噪声下线性随机近似的特殊实例。该方法在策略评估中的统计推断上表明该方法在分布上是一致的，并且包括数值实验，以证明该算法在跨一系列实际RL环境中在统计推断任务上的有效性。

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

使用Martingale浓度不平等，浓度界限为“从时间到$ n_0 $ on”是针对带有承包图的随机近似算法以及Martingale差异和Markov噪声的。这些应用于增强学习算法，尤其是异步Q学习和TD（0）。

重播缓冲区是许多强化学习方案中的关键组成部分。然而，他们的理论特性尚未完全理解。在本文中，我们分析了一个系统，将随机过程X推入重型缓冲区，然后随机采样以从重播缓冲区生成随机过程y。我们提供了采样过程的属性分析，例如平稳性，马尔可波和自相关，就原始过程的属性而言。我们的理论分析阐明了为什么重播缓冲液可能是良好的去率。我们的分析提供了理论工具，以证明基于重播缓冲算法的收敛性，这些算法在强化学习方案中很普遍。

我们考虑了两个玩家零和游戏的问题。这个问题在文献中制定为Min-Max Markov游戏。该游戏的解决方案是从给定状态开始的最小最大收益称为状态的最小值。在这项工作中，我们使用在文献中成功应用的连续放松技术​​来计算双球员零和游戏的解决方案，以在马尔可夫决策过程的上下文中计算更快的价值迭代算法。我们将连续放松的概念扩展到两个玩家零和游戏的设置。我们表明，在游戏的特殊结构下，该技术有助于更快地计算状态的最大值。然后，我们推导出一种广义的Minimax Q学习算法，当模型信息未知时计算最佳策略。最后，我们证明了利用随机近似技术的提议的广义Minimax Q学习算法的收敛性，在迭代的界限上的假设下。通过实验，我们展示了我们所提出的算法的有效性。

在本文中，我们提出了一种随机梯度算法，用于最大程度地减少对嘈杂成本样本的期望，而对于任何给定参数，则只观察到后者。我们的算法采用带有随机扰动的梯度估计方案，该方案是使用单位球体截断的cauchy分布形成的。我们分析了提出的梯度估计量的偏差和方差。发现我们的算法在目标函数是非凸且参数维度较高的情况下特别有用。从渐近收敛分析中，我们确定我们的算法几乎可以肯定地收敛到目标函数的固定点并获得渐近收敛速率。我们还表明，我们的算法避免了不稳定的平衡，这意味着与局部最小值的融合。此外，我们对我们的算法进行非反应收敛分析。特别是，我们在这里建立了一个非质子绑定，用于寻找非convex目标函数的$ \ epsilon $ stationary点。最后，我们通过模拟以数字方式证明我们的算法的性能在一些非凸面设置上优于GSF，SPSA和RDSA，并进一步验证其在凸（NOISY）目标上的性能。

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.

我们考虑由一般随机序列驱动的随机梯度下降（SGD）算法，包括I.I.D噪声和随机行走，在任意图上等等；并以渐近意义进行分析。具体而言，我们采用了“效率排序”的概念，这是一种分析的工具，用于比较马尔可夫链蒙特卡洛（MCMC）采样器的性能，以sgd算法的形式以与量表矩阵相关的loewner订购形式长期。使用此顺序，我们表明对MCMC采样更有效的输入序列也导致限制中SGD算法的误差的较小协方差。这也表明，当受到更有效的链驱动时，任意加权的SGD迭代的MSE迭代会变小。我们的发现在分散的优化和群学习等应用程序中特别感兴趣，其中SGD是在基础通信图上以随机步行方式实施的，以解决成本问题和/或数据隐私。我们证明了某些非马克维亚过程如何在基于典型的混合时间的非轴突界限上是棘手的，在SGD的效率订购意义上，可以超越其马尔可夫对应物。我们通过将其应用于梯度下降，并以洗牌和小批量梯度下降将其应用于梯度下降，从而显示了我们的方法的实用性，从而在统一框架下重申了现有文献的关键结果。从经验上讲，我们还观察到SGD的变体（例如加速SGD和Adam）的效率排序，开辟了将我们的效率订购概念扩展到更广泛的随机优化算法的可能性。

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

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