我们解决了加固学习的安全问题。我们在折扣无限地平线受限的Markov决策过程框架中提出了问题。现有结果表明,基于梯度的方法能够实现$ \ mathcal {o}(1 / \ sqrt {t})$全球收敛速度,用于最优差距和约束违规。我们展示了一种基于自然的基于政策梯度的算法,该算法具有更快的收敛速度$ \ mathcal {o}(\ log(t)/ t)$的最优性差距和约束违规。当满足Slater的条件并已知先验时,可以进一步保证足够大的$ T $的零限制违规,同时保持相同的收敛速度。
translated by 谷歌翻译
我们研究具有多个奖励价值函数的马尔可夫决策过程(MDP)的政策优化,应根据给定的标准共同优化,例如比例公平(平滑凹面标量),硬约束(约束MDP)和Max-Min Trade-离开。我们提出了一个改变锚定的正规自然政策梯度(ARNPG)框架,该框架可以系统地将良好表现的一阶方法中的思想纳入多目标MDP问题的策略优化算法的设计。从理论上讲,基于ARNPG框架的设计算法实现了$ \ tilde {o}(1/t)$全局收敛,并具有精确的梯度。从经验上讲,与某些现有的基于策略梯度的方法相比,ARNPG引导的算法在精确梯度和基于样本的场景中也表现出卓越的性能。
translated by 谷歌翻译
强化学习被广泛用于在与环境互动时需要执行顺序决策的应用中。当决策要求包括满足一些安全限制时,问题就变得更加具有挑战性。该问题在数学上是作为约束的马尔可夫决策过程(CMDP)提出的。在文献中,可以通过无模型的方式解决各种算法来解决CMDP问题,以实现$ \ epsilon $ - 最佳的累积奖励,并使用$ \ epsilon $可行的政策。 $ \ epsilon $可行的政策意味着它遭受了违规的限制。这里的一个重要问题是,我们是否可以实现$ \ epsilon $ - 最佳的累积奖励,并违反零约束。为此,我们主张使用随机原始偶对偶方法来解决CMDP问题,并提出保守的随机原始二重算法(CSPDA),该算法(CSPDA)显示出$ \ tilde {\ tilde {\ Mathcal {o}} \ left(1 /\ epsilon^2 \ right)$样本复杂性,以实现$ \ epsilon $ - 最佳累积奖励,违反零约束。在先前的工作中,$ \ epsilon $ - 最佳策略的最佳可用样本复杂性是零约束的策略是$ \ tilde {\ Mathcal {o}}} \ left(1/\ epsilon^5 \ right)$。因此,与最新技术相比,拟议的算法提供了重大改进。
translated by 谷歌翻译
我们考虑了在连续的状态行为空间中受到约束马尔可夫决策过程(CMDP)的问题,在该空间中,目标是最大程度地提高预期的累积奖励受到某些约束。我们提出了一种新型的保守自然政策梯度原始二算法(C-NPG-PD),以达到零约束违规,同时实现了目标价值函数的最新融合结果。对于一般策略参数化,我们证明了价值函数与全局最佳功能的融合到由于限制性策略类而导致的近似错误。我们甚至从$ \ Mathcal {o}(1/\ epsilon^6)$从$ \ Mathcal {o}(1/\ Epsilon^4)$提高了现有约束NPG-PD算法\ cite {ding2020}的样本复杂性。。据我们所知,这是第一项通过自然政策梯度样式算法建立零约束违规的工作,用于无限的地平线折扣CMDP。我们通过实验评估证明了提出的算法的优点。
translated by 谷歌翻译
我们考虑了具有未知成本函数的大规模马尔可夫决策过程,并解决了从有限一套专家演示学习政策的问题。我们假设学习者不允许与专家互动,并且无法访问任何类型的加固信号。现有的逆钢筋学习方法具有强大的理论保证,但在计算上是昂贵的,而最先进的政策优化算法实现了重大的经验成功,但受到有限的理论理解受到阻碍。为了弥合理论与实践之间的差距,我们使用拉格朗日二元介绍了一种新的Bilinear鞍点框架。所提出的原始双视点允许我们通过随机凸优化的镜头开发出无模型可释放的算法。该方法享有实现,低内存要求和独立于州数量的计算和采样复杂性的优点。我们进一步提出了同等的无悔在线学习解释。
translated by 谷歌翻译
受限的强化学习是最大程度地提高预期奖励受到公用事业/成本的限制。但是,由于建模错误,对抗性攻击,非平稳性,训练环境可能与测试环境不一样,导致严重的性能降级和更重要的违反约束。我们提出了一个在模型不确定性下的强大约束强化学习框架,其中MDP不是固定的,而是在某些不确定性集中,目的是确保在不确定性集中满足所有MDP的限制,并最大程度地满足对公用事业/成本的限制不确定性集中最差的奖励性能。我们设计了一种强大的原始双重方法,并在理论上进一步发展了其收敛性,复杂性和可行性的保证。然后,我们研究了$ \ delta $ - 污染不确定性集的具体示例,设计一种在线且无模型的算法,并理论上表征了其样本复杂性。
translated by 谷歌翻译
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.
translated by 谷歌翻译
我们重新审视了最简单的设置之一中的政策梯度方法的有限时间分析:有限状态和动作MDP,具有由所有随机策略组成的策略类和精确的渐变评估。有一些最近的工作将此设置视为平滑的非线性优化问题的实例,并显示具有小阶梯大小的子线性收敛速率。在这里,我们根据与政策迭代的连接采取不同的透视,并显示政策梯度方法的许多变体成功,阶梯大小大,并达到了线性收敛速率。
translated by 谷歌翻译
我们研究了平均奖励马尔可夫决策过程(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。我们的理论优势通过数值实验来证实。
translated by 谷歌翻译
政策优化,通过大规模优化技术最大化价值函数来学习兴趣的政策,位于现代强化学习(RL)的核心。除了价值最大化之外,其他实际考虑因素也出现,包括令人鼓舞的探索,以及确保由于安全,资源和运营限制而确保学习政策的某些结构性。这些考虑通常可以通过诉诸正规化的RL来占据,这增加了目标值函数,并通过结构促进正则化术语。专注于无限范围打折马尔可夫决策过程,本文提出了一种用于解决正规化的RL的广义策略镜血压(GPMD)算法。作为策略镜血压LAN的概括(2021),所提出的算法可以容纳一般类凸常规的常规阶级,以及在使用中的规则器的认识到的广泛的Bregman分歧。我们展示了我们的算法在整个学习速率范围内,以无维的方式在全球解决方案的整个学习速率范围内融合到全球解决方案,即使常规器缺乏强大的凸起和平滑度。此外,在不精确的策略评估和不完美的政策更新方面,该线性收敛特征是可透明的。提供数值实验以证实GPMD的适用性和吸引力性能。
translated by 谷歌翻译
策略梯度方法适用于复杂的,不理解的,通过对参数化的策略进行随机梯度下降来控制问题。不幸的是,即使对于可以通过标准动态编程技术解决的简单控制问题,策略梯度算法也会面临非凸优化问题,并且被广泛理解为仅收敛到固定点。这项工作确定了结构属性 - 通过几个经典控制问题共享 - 确保策略梯度目标函数尽管是非凸面,但没有次优的固定点。当这些条件得到加强时,该目标满足了产生收敛速率的Polyak-lojasiewicz(梯度优势)条件。当其中一些条件放松时,我们还可以在任何固定点的最佳差距上提供界限。
translated by 谷歌翻译
这项工作开发了具有严格效率的新算法,可确保无限的地平线模仿学习(IL)具有线性函数近似而无需限制性相干假设。我们从问题的最小值开始,然后概述如何从优化中利用经典工具,尤其是近端点方法(PPM)和双平滑性,分别用于在线和离线IL。多亏了PPM,我们避免了在以前的文献中出现在线IL的嵌套政策评估和成本更新。特别是,我们通过优化单个凸的优化和在成本和Q函数上的平稳目标来消除常规交替更新。当不确定地解决时,我们将优化错误与恢复策略的次级优势联系起来。作为额外的奖励,通过将PPM重新解释为双重平滑以专家政策为中心,我们还获得了一个离线IL IL算法,该算法在所需的专家轨迹方面享有理论保证。最后,我们实现了线性和神经网络功能近似的令人信服的经验性能。
translated by 谷歌翻译
Offline reinforcement learning (RL) concerns pursuing an optimal policy for sequential decision-making from a pre-collected dataset, without further interaction with the environment. Recent theoretical progress has focused on developing sample-efficient offline RL algorithms with various relaxed assumptions on data coverage and function approximators, especially to handle the case with excessively large state-action spaces. Among them, the framework based on the linear-programming (LP) reformulation of Markov decision processes has shown promise: it enables sample-efficient offline RL with function approximation, under only partial data coverage and realizability assumptions on the function classes, with favorable computational tractability. In this work, we revisit the LP framework for offline RL, and advance the existing results in several aspects, relaxing certain assumptions and achieving optimal statistical rates in terms of sample size. Our key enabler is to introduce proper constraints in the reformulation, instead of using any regularization as in the literature, sometimes also with careful choices of the function classes and initial state distributions. We hope our insights further advocate the study of the LP framework, as well as the induced primal-dual minimax optimization, in offline RL.
translated by 谷歌翻译
作为安全加强学习的重要框架,在最近的文献中已经广泛研究了受约束的马尔可夫决策过程(CMDP)。然而,尽管在各种式学习设置下取得了丰富的结果,但就算法设计和信息理论样本复杂性下限而言,仍然缺乏对离线CMDP问题的基本理解。在本文中,我们专注于仅在脱机数据可用的情况下解决CMDP问题。通过采用单极浓缩系数$ c^*$的概念,我们建立了一个$ \ omega \ left(\ frac {\ min \ left \ left \ weft \ {| \ mathcal {s} || \ mathcal {a} a} |,, | \ Mathcal {s} |+i \ right \} c^*} {(1- \ gamma)^3 \ epsilon^2} \ right)$ sample Complacy度在离线cmdp问题上,其中$ i $架对于约束数量。通过引入一种简单但新颖的偏差控制机制,我们提出了一种称为DPDL的近乎最佳的原始二重学习算法。该算法证明,除了$ \ tilde {\ Mathcal {o}}}}(((1- \ gamma)^{ - 1})$外,该算法可确保零约束违规及其样本复杂性匹配上下界。还包括有关如何处理未知常数$ c^*$以及离线数据集中潜在的异步结构的全面讨论。
translated by 谷歌翻译
本文分析了双模的彼此优化随机算法框架。 Bilevel优化是一类表现出两级结构的问题,其目标是使具有变量的外目标函数最小化,该变量被限制为对(内部)优化问题的最佳解决方案。我们考虑内部问题的情况是不受约束的并且强烈凸起的情况,而外部问题受到约束并具有平滑的目标函数。我们提出了一种用于解决如此偏纤维问题的两次时间尺度随机近似(TTSA)算法。在算法中,使用较大步长的随机梯度更新用于内部问题,而具有较小步长的投影随机梯度更新用于外部问题。我们在各种设置下分析了TTSA算法的收敛速率:当外部问题强烈凸起(RESP。〜弱凸)时,TTSA算法查找$ \ MATHCAL {O}(k ^ { - 2/3})$ -Optimal(resp。〜$ \ mathcal {o}(k ^ {-2/5})$ - 静止)解决方案,其中$ k $是总迭代号。作为一个应用程序,我们表明,两个时间尺度的自然演员 - 批评批评近端策略优化算法可以被视为我们的TTSA框架的特殊情况。重要的是,与全球最优政策相比,自然演员批评算法显示以预期折扣奖励的差距,以$ \ mathcal {o}(k ^ { - 1/4})的速率收敛。
translated by 谷歌翻译
我们考虑了折现成本约束的马尔可夫决策过程(CMDP)策略优化问题,其中代理商试图最大化折扣累计奖励,但受到折扣累积公用事业的许多限制。为了解决这个受约束的优化程序,我们研究了经典原始偶性方法的在线参与者 - 批判性变体,其中使用来自基本时间变化的马尔可夫过程产生的单个轨迹的样品估算了原始功能和双重函数的梯度。这种在线原始双重自然参与者批评算法维护并迭代更新三个变量:双变量(或拉格朗日乘数),一个原始变量(或actor)以及用于估算原始变量和偶变量的梯度的评论变量。这些变量同时更新,但在不同的时间尺度上(使用不同的步骤尺寸),它们都相互交织在一起。我们的主要贡献是得出该算法与CMDP问题全局最佳收敛的有限时间分析。具体而言,我们表明,在适当的步骤中,最佳差距和约束违规的情况下,以$ \ mathcal {o}(1/k^{1/6})$的价格收敛到零,其中k是数字。迭代。据我们所知,本文是第一个研究用于解决CMDP问题的在线原始偶发参与者方法的有限时间复杂性。我们还通过数值模拟来验证该算法的有效性。
translated by 谷歌翻译
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.
translated by 谷歌翻译
离线增强学习(RL)的样本效率保证通常依赖于对功能类别(例如Bellman-Completeness)和数据覆盖范围(例如,全政策浓缩性)的强有力的假设。尽管最近在放松这些假设方面做出了努力,但现有作品只能放松这两个因素之一,从而使另一个因素的强烈假设完好无损。作为一个重要的开放问题,我们是否可以实现对这两个因素的假设较弱的样本效率离线RL?在本文中,我们以积极的态度回答了这个问题。我们基于MDP的原始偶对偶进行分析了一种简单的算法,其中双重变量(打折占用)是使用密度比函数对离线数据进行建模的。通过适当的正则化,我们表明该算法仅在可变性和单极浓缩性下具有多项式样品的复杂性。我们还基于不同的假设提供了替代分析,以阐明离线RL原始二算法的性质。
translated by 谷歌翻译
非convex受限的优化问题可用于模拟许多机器学习问题,例如多级Neyman-Pearson分类和受限的Markov决策过程。但是,由于目标和约束可能是非概念,因此这些问题都是具有挑战性的,因此很难平衡减少损失价值和减少约束违规行为的平衡。尽管有几种方法可以解决此类问题,但它们都是双环或三环算法,它们需要Oracles来解决某些子问题,通过在每次迭代中调整多个超级参数,以达到某些准确性。在本文中,我们提出了一种新型的梯度下降和扰动的上升(GDPA)算法,以解决一类平滑的非概念不平等的限制问题。 GDPA是一种原始的偶算法,仅利用目标和约束函数的一阶信息,以交替的方式更新原始变量和双重变量。该算法的关键特征是它是一种单循环算法,其中只需要调整两个步骤尺寸。我们表明,在轻度的规律性条件下,GDPA能够找到非convex功能约束问题的Karush-Kuhn-Tucker(KKT)点,并保证了收敛率。据我们所知,这是第一个可以通过非convex不等式约束来解决一般非凸的平滑问题的单循环算法。与最著名的算法相比,数值结果还显示了GDPA的优越性(就平稳性测量和获得的溶液的可行性而言)。
translated by 谷歌翻译
二重优化发现在现代机器学习问题中发现了广泛的应用,例如超参数优化,神经体系结构搜索,元学习等。而具有独特的内部最小点(例如,内部功能是强烈凸的,都具有唯一的内在最小点)的理解,这是充分理解的,多个内部最小点的问题仍然是具有挑战性和开放的。为此问题设计的现有算法适用于限制情况,并且不能完全保证融合。在本文中,我们采用了双重优化的重新制定来限制优化,并通过原始的双二线优化(PDBO)算法解决了问题。 PDBO不仅解决了多个内部最小挑战,而且还具有完全一阶效率的情况,而无需涉及二阶Hessian和Jacobian计算,而不是大多数现有的基于梯度的二杆算法。我们进一步表征了PDBO的收敛速率,它是与多个内部最小值的双光线优化的第一个已知的非质合收敛保证。我们的实验证明了所提出的方法的预期性能。
translated by 谷歌翻译