我们重新审视了最简单的设置之一中的政策梯度方法的有限时间分析：有限状态和动作MDP，具有由所有随机策略组成的策略类和精确的渐变评估。有一些最近的工作将此设置视为平滑的非线性优化问题的实例，并显示具有小阶梯大小的子线性收敛速率。在这里，我们根据与政策迭代的连接采取不同的透视，并显示政策梯度方法的许多变体成功，阶梯大小大，并达到了线性收敛速率。

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

民间传说表明，政策梯度比其相对，近似政策迭代更为强大。本文研究了国家聚集表示的案例，该案例是对状态空间进行分区的情况，并且在分区上保持了策略或价值函数近似。本文显示了一种策略梯度方法收敛到政策，该政策的遗憾是由$ \ epsilon $界定的，这是属于公共分区的国家行动值函数的两个要素之间的最大区别。通过相同的表示，近似政策迭代和近似价值迭代都可以产生政策，其遗憾的比例为$ \ epsilon/（1- \ gamma）$，其中$ \ gamma $是折扣因子。面对固有的近似误差，局部优化真实决策目标的方法可以更加健壮。

政策优化，通过大规模优化技术最大化价值函数来学习兴趣的政策，位于现代强化学习（RL）的核心。除了价值最大化之外，其他实际考虑因素也出现，包括令人鼓舞的探索，以及确保由于安全，资源和运营限制而确保学习政策的某些结构性。这些考虑通常可以通过诉诸正规化的RL来占据，这增加了目标值函数，并通过结构促进正则化术语。专注于无限范围打折马尔可夫决策过程，本文提出了一种用于解决正规化的RL的广义策略镜血压（GPMD）算法。作为策略镜血压LAN的概括（2021），所提出的算法可以容纳一般类凸常规的常规阶级，以及在使用中的规则器的认识到的广泛的Bregman分歧。我们展示了我们的算法在整个学习速率范围内，以无维的方式在全球解决方案的整个学习速率范围内融合到全球解决方案，即使常规器缺乏强大的凸起和平滑度。此外，在不精确的策略评估和不完美的政策更新方面，该线性收敛特征是可透明的。提供数值实验以证实GPMD的适用性和吸引力性能。

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.

我们解决了加固学习的安全问题。我们在折扣无限地平线受限的Markov决策过程框架中提出了问题。现有结果表明，基于梯度的方法能够实现$ \ mathcal {o}（1 / \ sqrt {t}）$全球收敛速度，用于最优差距和约束违规。我们展示了一种基于自然的基于政策梯度的算法，该算法具有更快的收敛速度$ \ mathcal {o}（\ log（t）/ t）$的最优性差距和约束违规。当满足Slater的条件并已知先验时，可以进一步保证足够大的$ T $的零限制违规，同时保持相同的收敛速度。

我们研究具有多个奖励价值函数的马尔可夫决策过程（MDP）的政策优化，应根据给定的标准共同优化，例如比例公平（平滑凹面标量），硬约束（约束MDP）和Max-Min Trade-离开。我们提出了一个改变锚定的正规自然政策梯度（ARNPG）框架，该框架可以系统地将良好表现的一阶方法中的思想纳入多目标MDP问题的策略优化算法的设计。从理论上讲，基于ARNPG框架的设计算法实现了$ \ tilde {o}（1/t）$全局收敛，并具有精确的梯度。从经验上讲，与某些现有的基于策略梯度的方法相比，ARNPG引导的算法在精确梯度和基于样本的场景中也表现出卓越的性能。

我们考虑解决强大的马尔可夫决策过程（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问题的基于策略的一阶方法的新事物。

We study the convergence of several natural policy gradient (NPG) methods in infinite-horizon discounted Markov decision processes with regular policy parametrizations. For a variety of NPGs and reward functions we show that the trajectories in state-action space are solutions of gradient flows with respect to Hessian geometries, based on which we obtain global convergence guarantees and convergence rates. In particular, we show linear convergence for unregularized and regularized NPG flows with the metrics proposed by Kakade and Morimura and co-authors by observing that these arise from the Hessian geometries of conditional entropy and entropy respectively. Further, we obtain sublinear convergence rates for Hessian geometries arising from other convex functions like log-barriers. Finally, we interpret the discrete-time NPG methods with regularized rewards as inexact Newton methods if the NPG is defined with respect to the Hessian geometry of the regularizer. This yields local quadratic convergence rates of these methods for step size equal to the penalization strength.

We propose a new policy gradient method, named homotopic policy mirror descent (HPMD), for solving discounted, infinite horizon MDPs with finite state and action spaces. HPMD performs a mirror descent type policy update with an additional diminishing regularization term, and possesses several computational properties that seem to be new in the literature. We first establish the global linear convergence of HPMD instantiated with Kullback-Leibler divergence, for both the optimality gap, and a weighted distance to the set of optimal policies. Then local superlinear convergence is obtained for both quantities without any assumption. With local acceleration and diminishing regularization, we establish the first result among policy gradient methods on certifying and characterizing the limiting policy, by showing, with a non-asymptotic characterization, that the last-iterate policy converges to the unique optimal policy with the maximal entropy. We then extend all the aforementioned results to HPMD instantiated with a broad class of decomposable Bregman divergences, demonstrating the generality of the these computational properties. As a by product, we discover the finite-time exact convergence for some commonly used Bregman divergences, implying the continuing convergence of HPMD to the limiting policy even if the current policy is already optimal. Finally, we develop a stochastic version of HPMD and establish similar convergence properties. By exploiting the local acceleration, we show that for small optimality gap, a better than $\tilde{\mathcal{O}}(\left|\mathcal{S}\right| \left|\mathcal{A}\right| / \epsilon^2)$ sample complexity holds with high probability, when assuming a generative model for policy evaluation.

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

政策优化是设计强化学习算法的基本原则，一个例子是具有剪切的替代物镜（PPO-CLIP）的近端政策优化算法（PPO-CLIP），由于其简单性和有效性，该算法已被普遍用于深度强化学习。尽管具有出色的经验表现，但PPO-CLIP尚未通过最新的理论证明是合理的。在本文中，我们在神经功能近似下建立了PPO-CLIP的第一个全局收敛速率。我们确定分析PPO-CLIP的基本挑战并用两个核心思想解决：（i）我们从铰链损失的角度重新解释了PPO-CLIP，这将政策改进与解决铰链损失和铰链损失和铰链损失和铰链分类问题的联系联系起来。提供PPO-CLIP目标的广义版。 （ii）基于上面的观点，我们提出了一个两步的策略改进方案，该方案通过熵镜下降和基于回归的策略更新方案从复杂的神经策略参数借助复杂的神经策略参数化来促进收敛分析。此外，我们的理论结果提供了剪辑机理对PPO-CLIP收敛的影响的首次表征。通过实验，我们从经验上验证了PPO-CLIP的重新解释，并在各种RL基准任务上具有各种分类器的广义目标。

深度加强学习的最近成功的大部分是由正常化的政策优化（RPO）算法驱动，具有跨多个域的强大性能。在这家族的方法中，代理经过培训，以在惩罚某些引用或默认策略的行为中的偏差时最大化累积奖励。除了经验的成功外，还有一个强大的理论基础，了解应用于单一任务的RPO方法，与自然梯度，信任区域和变分方法有关。但是，对于多任务设置中的默认策略，对所需属性的正式理解有限，越来越重要的域作为现场转向培训更有能力的代理商。在这里，我们通过将默认策略的质量与其对优化的影响正式链接到其对其影响的效果方面，进行第一步才能填补这种差距。使用这些结果，我们将获得具有强大性能保证的多任务学习的原则性的RPO算法。

在本文中，我们提出了一种新的策略梯度（PG）方法，即用于解决一类正规化加固学习（RL）问题的块策略镜下降（BPMD）方法（强烈） - convex正规化器。与带有批处理更新规则的传统PG方法（访问和更新每个状态的策略）相比，BPMD方法通过部分更新规则具有廉价的每卷计算，该规则在采样状态上执行策略更新。尽管问题的性质和部分更新规则具有非概念性质，但我们还是为多种采样方案提供了统一的分析，并表明BPMD可以实现快速的线性收敛到全局最优性。特别是，均匀的采样导致可比的最坏情况总计算复杂性与批处理PG方法。还确定了一种与上policy采样的必要条件。通过混合采样方案，我们进一步表明，BPMD具有潜在的实例依赖性加速度，从而改善了对状态空间的依赖性，因此优于批次PG方法。然后，我们通过利用从样品构建的随机一阶信息扩展到随机设置。使用生成模型，$ \ tilde {\ mathcal {o}}（\ left \ lvert \ lerver \ mathcal {s} \ right \ rvert \ rvert \ left \ lest \ lerver \ lovt \ mathcal {a} \ right \ right \ rvert \ rvert \ rvert /\ epsilon） $ \ tilde {\ mathcal {o}}（\ left \ lvert \ m athcal {s} \ right \ rvert \ rvert \ left \ lest \ lvert \ lerver \ mathcal {a} \ right \ right \ rvert /\ epsilon^2）强率强度（分别为非巧克力符号）正规化器，其中$ \ epsilon $表示目标准确性。据我们所知，这是第一次开发和分析了块坐标下降方法，以进行强化学习的策略优化，这为解决大规模RL问题提供了新的观点。

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

Reinforcement learning (RL) problems over general state and action spaces are notoriously challenging. In contrast to the tableau setting, one can not enumerate all the states and then iteratively update the policies for each state. This prevents the application of many well-studied RL methods especially those with provable convergence guarantees. In this paper, we first present a substantial generalization of the recently developed policy mirror descent method to deal with general state and action spaces. We introduce new approaches to incorporate function approximation into this method, so that we do not need to use explicit policy parameterization at all. Moreover, we present a novel policy dual averaging method for which possibly simpler function approximation techniques can be applied. We establish linear convergence rate to global optimality or sublinear convergence to stationarity for these methods applied to solve different classes of RL problems under exact policy evaluation. We then define proper notions of the approximation errors for policy evaluation and investigate their impact on the convergence of these methods applied to general-state RL problems with either finite-action or continuous-action spaces. To the best of our knowledge, the development of these algorithmic frameworks as well as their convergence analysis appear to be new in the literature.

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.

强大的马尔可夫决策过程（MDP）用于在不确定环境中的动态优化应用，并已进行了广泛的研究。 MDP的许多主要属性和算法（例如价值迭代和策略迭代）直接扩展到RMDP。令人惊讶的是，没有已知的MDP凸优化公式用于求解RMDP。这项工作描述了在经典的SA截形和S型角假设下RMDP的第一个凸优化公式。我们通过使用熵正则化和变量的指数变化来得出具有线性数量和约束的线性数量的凸公式。我们的公式可以与来自凸优化的有效方法结合使用，以获得以不确定概率求解RMDP的新算法。我们进一步简化了使用多面体不确定性集的RMDP的公式。我们的工作打开了RMDP的新研究方向，可以作为获得RMDP的可拖动凸公式的第一步。

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

本文从凸优化的角度研究了已知和未知环境中的随机最短路径（SSP）问题。它首先回忆起已知参数案例的结果，并通过不同的证据发展理解。然后，它着重于未知的参数情况，其中它研究了扩展价值迭代（EVI）运算符。这包括Rosenberg等人中使用的现有操作员。 [26]和Tarbouriech等。 [31]基于L-1规范和至上规范，以及定义与其他规范和差异相对应的EVI操作员，例如KL-Divergence。本文总的来说，EVI操作员如何与凸面程序及其双重形式相关联，这些形式表现出强烈的双重性。然后，本文重点介绍了NEU和Pike-Burke [21]的有限视野研究的界限是否可以应用于SSP设置中的这些扩展价值迭代操作员。它表明存在与[21]的相似界限，但是它们会导致不在一般单调且具有更复杂收敛属性的运算符。在特殊情况下，我们观察到振荡行为。本文通过几个需要进一步检查的示例，就研究的进展产生了公开问题。