我们研究了随机近似的分散变体，这是一种数据驱动的方法，用于在嘈杂的测量中找到操作员的根。一个具有自己的操作员和数据观察的代理网络，合作地通过分散的通信图找到了聚合操作员的固定点。我们的主要贡献是在从马尔可夫过程中采样时在每个代理下观察到的数据时，对这种分散的随机近似方法提供有限的时间分析；这种缺乏独立性使迭代率偏向和（可能）无限。在相当标准的假设下，我们表明所提出方法的收敛速率与样本是独立的基本相同，仅由对数因子的差异而不同，该对数因素是说明了马尔可夫过程的混合时间。我们的分析中的关键思想是引入一种新型的Razumikhin-Lyapunov函数，该功能是由用于分析延迟普通微分方程的稳定性的一种动机。我们还讨论了拟议方法在多代理系统中许多有趣的学习问题上的应用。

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.

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

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

我们考虑分散的优化问题，其中许多代理通过在基础通信图上交换来最大程度地减少其本地功能的平均值。具体而言，我们将自己置于异步模型中，其中只有一个随机部分在每次迭代时执行计算，而信息交换可以在所有节点之间进行，并以不对称的方式进行。对于此设置，我们提出了一种算法，该算法结合了整个网络上梯度跟踪和差异的差异。这使每个节点能够跟踪目标函数梯度的平均值。我们的理论分析表明，在预期混合矩阵的轻度连通性条件下，当局部目标函数强烈凸面时，算法会汇聚。特别是，我们的结果不需要混合矩阵是双随机的。在实验中，我们研究了一种广播机制，该机制将信息从计算节点传输到其邻居，并确认我们方法在合成和现实世界数据集上的线性收敛性。

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

多智能体增强学习（Marl）最近引起了很多研究。然而，与其单一代理对应物不同，Marl的许多理论和算法方面尚未得到很好的理解。在本文中，我们使用演员 - 评论家（AC）算法研究了自主代理的协调行为的出现。具体而言，我们提出并分析了一类协调的演员 - 批评算法（CAC），其中单独的参数化政策有一个{\ IT共享}部分（其中在所有代理中共同优化）和{\ IT个性化}部分（这是只有当地优化）。这种类型的{\它部分个性化}策略允许代理通过利用同伴的过去的经验来学习协调并适应各个任务。我们设计的灵活性允许提出的Marl-CAC算法用于{\ IT完全分散}设置中使用，其中代理商只能与其邻居通信，以及偶尔代理的{\ IT联合}设置与服务器通信，同时优化其（部分个性化）本地模型。从理论上讲，在一些标准规律性假设下，所提出的Marl-CAC算法需要$ \ mathcal {o}（\ epsilon ^ { - \ frac {5} {2}}）$样本来实现$ \ epsilon $ - 固定式解决方案（定义为目标函数梯度的平方标准的解决方案小于$ \ epsilon $）。据我们所知，这项工作为具有部分个性化策略的分散式交流算法提供了第一个有限的样本保证。

分散的参与者 - 批评（AC）算法已被广泛用于多机构增强学习（MARL），并取得了杰出的成功。除了其经验成功之外，分散的AC算法的理论收敛性在很大程度上没有探索。现有的有限时间收敛结果是基于双环更新或两次尺度的步骤规则得出的，这在实际实施中不经常采用。在这项工作中，我们介绍了一种完全分散的AC算法，演员，评论家和全球奖励估算器以交替的方式更新，阶跃尺寸的顺序相同，即，我们采用\ emph {single-emph {single-timesscale}更新。从理论上讲，使用线性近似进行价值和奖励估计，我们表明我们的算法具有$ \ tilde {\ Mathcal {o}}}（\ epsilon^{ - 2}）$的样本复杂性，在马尔可夫式采样下与最佳复杂性相匹配双环实现（在此，$ \ tilde {\ Mathcal {o}} $隐藏了日志项）。样本复杂性可以提高到$ {\ Mathcal {o}}（\ epsilon^{ - 2}）$下的I.I.D.采样方案。建立我们的复杂性结果的核心是\ emph {我们揭示的最佳评论家变量的隐藏平滑度}。我们还提供了算法及其分析的本地动作隐私版本。最后，我们进行实验，以显示我们算法优于现有的分散AC算法的优势。

当数据自然分配到通过基础图的代理商之间，分散学习提供了隐私和沟通效率。通过过度参数化的学习设置，在该设置中，在该设置中训练了零训练损失，我们研究了分散学习的分散学习算法和概括性能，并在可分离的数据上下降。具体而言，对于分散的梯度下降（DGD）和各种损失函数，在无穷大（包括指数损失和逻辑损失）中渐近为零，我们得出了新的有限时间泛化界限。这补充了一长串最近的工作，该工作研究了概括性能和梯度下降的隐含偏见，而不是可分离的数据，但迄今为止，梯度下降的偏见仅限于集中学习方案。值得注意的是，我们的概括范围匹配其集中式同行。这背后的关键和独立感兴趣的是，在一类自我结合的损失方面建立了关于训练损失和DGD的传记率的新界限。最后，在算法方面，我们设计了改进的基于梯度的例程，可分离数据，并在经验上证明了训练和概括性能方面的加速命令。

培训期间的对抗性攻击能够强烈影响多功能增强学习算法的性能。因此，非常希望增加现有算法，使得消除对抗对协作网络的对抗性攻击的影响，或者至少有界限。在这项工作中，我们考虑一个完全分散的网络，每个代理商收到本地奖励并观察全球州和行动。我们提出了一种基于弹性共识的演员 - 批评算法，其中每个代理估计了团队平均奖励和价值函数，并将关联的参数向量传送到其立即邻居。我们表明，在拜占庭代理人的存在下，其估算和通信策略是完全任意的，合作社的估计值会融合到有概率一体的有界共识值，条件是在附近的最多有$ H $拜占庭代理商每个合作社和网络都是$（2h + 1）$ - 强大。此外，我们证明，合作社的政策在其团队平均目标函数的局部最大化器周围汇聚在其团队平均目标函数的概率上，这是对渐关节转移变得稳定的普发因子的政策。

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

在互联网上的多种代理环境中的新兴应用程序，如互联网，网络传感，自主系统和联合学习，呼叫分散算法，以便在计算和通信方面是资源有效的有限总和优化。在本文中，我们考虑了原型设置，其中代理正在协作地工作，以通过在预定的网络拓扑中与其邻居通信来最小化局部损失函数的总和。我们开发了一种新的算法，称为分散的随机递归梯度方法（DESTRess），用于非耦合有限和优化，它与集中式算法的最佳增量一阶Oracle（IFO）复杂性匹配，用于查找一阶静止点，同时保持通信效率。详细的理论和数值比较证实了迭代在广泛的参数制度上提高现有分散算法的资源效率。 Descress利用了多个关键算法设计思路，包括随机激活的随机递增渐变渐变更新，具有用于本地计算的迷你批次，梯度跟踪，梯度跟踪，用于额外混合（即，多个八卦轮），用于偏移通信，以及仔细选择超参数和新的分析框架可证明达到理想的计算 - 通信权衡。

我们提出了一种新的多功能增强学习的新型政策梯度方法，其利用了两个不同的差异减少技术，并且不需要在迭代上进行大量批次。具体而言，我们提出了一种基于势头的分散策略梯度跟踪（MDPGT），其中使用新的基于动量的方差减少技术来接近具有重要性采样的本地策略梯度代理，并采用中间参数来跟踪两个连续的策略梯度代理。此外，MDPGT可证明$ \ mathcal {o}的最佳可用样本复杂性（n ^ { - 1} \ epsilon ^ {-3}）$，用于汇聚到全球平均值的$ \ epsilon $ -stationary点n $本地性能函数（可能是非旋转）。这优于在分散的无模型增强学习中的最先进的样本复杂性，并且当用单个轨迹初始化时，采样复杂性与现有的分散的政策梯度方法获得的样本复杂性匹配。我们进一步验证了高斯策略函数的理论索赔。当所需的误差容忍$ \ epsilon $足够小时，MDPGT导致线性加速，以前已经在分散的随机优化中建立，但不是为了加强学习。最后，我们在多智能体增强学习基准环境下提供了实证结果，以支持我们的理论发现。

We study a multi-agent reinforcement learning (MARL) problem where the agents interact over a given network. The goal of the agents is to cooperatively maximize the average of their entropy-regularized long-term rewards. To overcome the curse of dimensionality and to reduce communication, we propose a Localized Policy Iteration (LPI) algorithm that provably learns a near-globally-optimal policy using only local information. In particular, we show that, despite restricting each agent's attention to only its $\kappa$-hop neighborhood, the agents are able to learn a policy with an optimality gap that decays polynomially in $\kappa$. In addition, we show the finite-sample convergence of LPI to the global optimal policy, which explicitly captures the trade-off between optimality and computational complexity in choosing $\kappa$. Numerical simulations demonstrate the effectiveness of LPI.

用于解决无约束光滑游戏的两个最突出的算法是经典随机梯度下降 - 上升（SGDA）和最近引入的随机共识优化（SCO）[Mescheder等，2017]。已知SGDA可以收敛到特定类别的游戏的静止点，但是当前的收敛分析需要有界方差假设。 SCO用于解决大规模对抗问题，但其收敛保证仅限于其确定性变体。在这项工作中，我们介绍了预期的共同胁迫条件，解释了它的好处，并在这种情况下提供了SGDA和SCO的第一次迭代收敛保证，以解决可能是非单调的一类随机变分不等式问题。我们将两种方法的线性会聚到解决方案的邻域时，当它们使用恒定的步长时，我们提出了富有识别的步骤化切换规则，以保证对确切解决方案的融合。此外，我们的收敛保证在任意抽样范式下担保，因此，我们对迷你匹配的复杂性进行了解。

在本文中，我们考虑了在$ N $代理的分布式优化问题，每个都具有本地成本函数，协作最小化连接网络上的本地成本函数的平均值。为了解决问题，我们提出了一种分布式随机重新洗脱（D-RR）算法，该算法结合了经典分布式梯度下降（DGD）方法和随机重新洗脱（RR）。我们表明D-RR继承了RR的优越性，以使光滑强凸和平的非凸起目标功能。特别是，对于平稳强凸的目标函数，D-RR在平方距离方面实现$ \ Mathcal {o}（1 / T ^ 2）$汇率（这里，$ t $计算迭代总数）在迭代和独特的最小化之间。当假设客观函数是平滑的非凸块并且具有Lipschitz连续组件函数时，我们将D-RR以$ \ Mathcal {O}的速率驱动到0美元的平方标准（1 / T ^ {2 / 3}）$。这些收敛结果与集中式RR（最多常数因素）匹配。

Decentralized bilevel optimization has received increasing attention recently due to its foundational role in many emerging multi-agent learning paradigms (e.g., multi-agent meta-learning and multi-agent reinforcement learning) over peer-to-peer edge networks. However, to work with the limited computation and communication capabilities of edge networks, a major challenge in developing decentralized bilevel optimization techniques is to lower sample and communication complexities. This motivates us to develop a new decentralized bilevel optimization called DIAMOND (decentralized single-timescale stochastic approximation with momentum and gradient-tracking). The contributions of this paper are as follows: i) our DIAMOND algorithm adopts a single-loop structure rather than following the natural double-loop structure of bilevel optimization, which offers low computation and implementation complexity; ii) compared to existing approaches, the DIAMOND algorithm does not require any full gradient evaluations, which further reduces both sample and computational complexities; iii) through a careful integration of momentum information and gradient tracking techniques, we show that the DIAMOND algorithm enjoys $\mathcal{O}(\epsilon^{-3/2})$ in sample and communication complexities for achieving an $\epsilon$-stationary solution, both of which are independent of the dataset sizes and significantly outperform existing works. Extensive experiments also verify our theoretical findings.

由于众所周知，强化学习算法是数据密集型的，因此从环境中进行采样观测的任务通常在多个代理之间分配。但是，将这些观察结果从代理转移到中心位置可能会非常昂贵，并且还可以损害每个代理人本地行为政策的隐私。在本文中，我们考虑了一个联合加强学习框架，其中多个代理商协作学习了一个全球模型，而无需共享他们的个人数据和政策。每个代理都维护模型的本地副本，并使用本地采样数据对其进行更新。尽管具有n个代理可以启用n次数据的采样，但尚不清楚它是否导致比例收敛的加速。我们提出了联合版本的On-Policy TD，Off-Policy TD和Q学习，并分析其收敛性。对于所有这些算法，据我们所知，我们是第一个考虑马尔可夫噪声和多个局部更新的人，并证明相对于代理的数量是线性收敛的速度。为了获得这些结果，我们表明联邦TD和Q学习是与马尔可夫噪声联合随机近似的一般框架的特殊情况，并且我们利用该框架提供了适用于所有算法的统一收敛分析。

遗憾已被广泛用作评估分布式多代理系统在线优化算法的性能的首选指标。但是，与代理相关的数据/模型变化可以显着影响决策，并需要在代理之间达成共识。此外，大多数现有的作品都集中在开发（强烈或非严格地）凸出的方法上，对于一般非凸损失的分布式在线优化中的遗憾界限，几乎没有得到很少的结果。为了解决这两个问题，我们提出了一种新型的综合遗憾，并使用新的基于网络的基于遗憾的度量标准来评估分布式在线优化算法。我们具体地定义了复合遗憾的静态和动态形式。通过利用我们的综合遗憾的动态形式，我们开发了一种基于共识的在线归一化梯度（CONGD）的伪convex损失方法，事实证明，它显示了与最佳器路径变化的规律性术语有关的透明性行为。对于一般的非凸损失，我们首先阐明了基于最近进步的分布式在线非凸学习的遗憾，因此没有确定性算法可以实现sublinear的遗憾。然后，我们根据离线优化的Oracle开发了分布式的在线非凸优化（Dinoco），而无需进入梯度。迪诺科（Dinoco）被证明是统一的遗憾。据我们所知，这是对一般分布在线非convex学习的第一个遗憾。

分散和联合学习的关键挑战之一是设计算法，这些算法有效地处理跨代理商的高度异构数据分布。在本文中，我们在数据异质性下重新审视分散的随机梯度下降算法（D-SGD）的分析。我们在D-SGD的收敛速率上展示了新数量的关键作用，称为\ emph {邻居异质性}。通过结合通信拓扑结构和异质性，我们的分析阐明了这两个分散学习中这两个概念之间的相互作用较低。然后，我们认为邻里的异质性提供了一种自然标准，可以学习数据依赖性拓扑结构，以减少（甚至可以消除）数据异质性对D-SGD收敛时间的有害影响。对于与标签偏度分类的重要情况，我们制定了学习这样一个良好拓扑的问题，例如我们使用Frank-Wolfe算法解决的可拖动优化问题。如一组模拟和现实世界实验所示，我们的方法提供了一种设计稀疏拓扑的方法，可以在数据异质性下平衡D-SGD的收敛速度和D-SGD的触电沟通成本。