零约束违反下的原始-对偶约束强化学习算法改进

+v：mala2255获取更多论文1.OOO.OOO基于原始-对偶方法的约束强化学习零约束违反白琴波普劳德大学电气与计算机工程系West Lafayette，IN 47906，美国阿姆里特·辛格·贝迪美国陆军研究实验室@ PURDUE. EDUAMRIT0714@GMAIL.COMMridulAgarwalAGARW 180@PURDUE. EDU电气和计算机工程系普鲁德大学West Lafayette，IN 47906，美国亚历克·科佩尔美国陆军研究实验室亚历克E. 科佩尔CIV@MAIL。密耳VaneetAggarwalVANEET @ PURDUE. EDU普劳德大学工业工程系West Lafayette，IN 47906，美国编辑：摘要强化学习广泛应用于需要在与环境交互时执行顺序决策的应用当决策要求包括满足一些安全约束时，问题变得更具该问题在数学上表示为约束马尔可夫决策过程（CMDP）。在文献中，各种算法可用于以无模型的方式来解决CMDP问题，以实现具有非线性可行策略的非线性最优累积奖励一个可行的策略意味着它遭受约束违反。这里的一个重要问题是，我们是否可以在零约束违反的情况下实现最优累积奖励。为了实现这一点，我们提倡使用随机原始-对偶方法来解决CMDP问题，并提出了一个保守的随机原始-对偶算法（CSPDA），该算法表现出在零约束条件下实现最优累积报酬的样本复杂度为1001/1002违规在先前的工作中，最好的可用样本复杂度的最优策略与零约束违反是101/105。 因此，与现有技术相比，所提出的算法提供了显著的改进保留字： 约束强化学习，原始-对偶，零违规1. 介绍强化学习（RL）是一种机器学习框架，它通过与环境反复交互来该框架被广泛用于arXiv：2109.06332v1 [cs.LG] 2021年9月+v：mala2255获取更多论文2.Σ.Σ广泛的应用，如机器人技术，通信，计算机视觉，自动驾驶等Arulkiraran et al.（ 2017 ） ;Kiran et al. （ 2021 ） 。 该 问 题 在 数 学 上 被 表 述 为 马 尔 可 夫 决 策 过 程（MDP），该过程由状态、动作和在采取特定动作后从一个状态到另一个状态的转移概率组成。在采取行动时，会获得奖励，总体目标是最大化折扣奖励的总和。然而，在各种现实环境中，智能体需要决定需要满足某些约束的动作（例如，平均功率约束在无线传感器网络中，Buratti et al. （2009），队列稳定性约束Xiang et al.（2015），safe explorationMoldovan and Abbeel（2012）， etc.）。配备有约束的成本函数的标准MDP被称为约束马尔可夫决策过程（CMDP）框架Altman（1999）。Altman（1999）指出，CMDP问题可以等价地写成线性规划（LP），因此在文献中可以找到有效的算法。但是，为了解决LP，需要访问环境的转移概率，这是在现实环境中不可用的，因此需要有效的方法来开发CMDP的无模型算法文献中提出了各种算法来解决CMDP问题，其中-先验知识的转移概率（见表1的比较）。这些算法的性能是衡量的样本数（状态动作状态转换），需要实现最优（目标次优）的可行（约束违反）的政策。一个完全可行的策略意味着所得到的策略不完全满足约束条件.然而，在许多应用中，例如在电力系统中，Vu等人。（2020）或自主车辆控制Wen et al. （2020），违反约束可能是灾难性的。因此，实现最优的目标保证，而不违反约束是一个重要的问题，是本文的重点。更确切地说，我们问的问题，“是否有可能实现最佳的次线性收敛速度的目标，同时实现零约束违反CMDP问题的先验知识的转移概率？“我们在这项工作中肯定地回答了上述问题。我们注意到，在这项工作中的样本复杂性结果表现出对状态和动作空间的基数的紧密依赖性（参见。表1）。主要贡献可归纳如下：• 据我们所知，这项工作是第一次尝试解决CMDPs，以实现零约束违反的最佳样本复杂度。在文献中存在一个例外，其以O/1/15的样本复杂度为代价来实现零违反，以达到最优策略。（2021年）。与此相反，我们能够以O·1/O·2的样本复杂度来实现零约束违反。• 我们利用对偶域中保守约束的思想来推导零约束违反。最近，Akhtar等人用保守约束来表示在线约束凸优化中的零约束违反。（2021），而CMDP问题比在线约束优化更具挑战性。然后，利用这项工作所特有的新颖分析，使用双重约束违反来推导原始域结果秒5.3）。我们注意到，直接应用保守约束的思想在原始区域不会导致最佳的依赖折扣因子。+v：mala2255获取更多论文3算法样品复杂性约束违反生成模型基于模型Efroni等. （2020年）1噢，|S|2|一|Σ（1−γ）32.ΣO（）没有Efroni等. （2020年）1O|S|2|一|（1−γ）32.ΣO（）没有Kalagarlaet al. （2021年）2O|S|3|一|（1−γ）32.ΣO（）没有ConRL Bran tley等. （2020年）O|S|2|一|（1−γ）62.ΣO（）没有OptPess-PrimalDual Liu等. （2021年）O|S|3|一|（1−γ）4π2.ΣO（2）没有OPDOP Ding et al. （2021年）O|S|2|一|（1−γ）4π2.ΣO（）没有He et al. （2021年）O（一）|S|γ|A）3|є2−.ΣN/A没有无模型NPG-PDDing等. （2020年）3O（一）|S|γ|A）5|є2−.ΣO（）是的CRPOXu et al. （2021年）4O（一）|S|γ|A）7|є4−.ΣO（）是的Prosecutor et al. （2021年）5O142（1−γ）π.ΣO（）是的Wei et al. （ 2021年）O|S|二、5|一|二、5（1− γ）18. 5є5.Σ零没有随机O（一）|S|γ|A）4|є2−.ΣN/A是的CSPDA（本工作，定理7）6O（一）|S|γ|A）4|є2−.Σ零是的下界Latestival和Hutter（2012）和Azar等人（ 二零一三年）Ω˜（一）|S|γ|A）3|є2−N/AN/A表1：该表总结了CMDPs文献中可用的不同基于模型和无模型的最新算法。我们注意到，在这项工作中，所提出的算法是能够实现最佳的样本复杂度，同时实现零约束违反以及。对于考虑不同背景的作品，如情节背景，我们提供了一个详细的方法将结果转换为形式附录A中的无限水平设置中的样本复杂度。• 所提出的算法利用自适应状态-动作对采样（cf.当量（12）），由于随机梯度估计表现出无界的二阶矩。这使得分析具有挑战性，并且不能使用标准鞍点算法。这种困难是通过使用KL分歧作为性能指标的双重更新类似于张等人。（2021年）。• 我们已经进行了概念验证实验，以支持理论研究结果。1. Efroni等人（2020）使用N，其是跨2. Kalagarla等人（2021）使用C，这是状态-动作对的可能后继状态数量的上限。我们用S来约束它。3. 我们使用Ding等人定理4中的结果。（2020年）。 注意，在他们论文的算法2中，|一||每个外环都需要样本。|samples are necessary for each outer loop.1−γ4. 注意，在Xu et al. （2021）中，需要一个具有K in迭代的内循环来进行多项式估计，并且Kin=O（T）（1− γ）|S||一|5. 在Chen等人（2021）中，对S，A的依赖性不明确。该算法需要对Q函数进行估计。然而，作者6. 请注意，本文中定义的值函数是一个规范化版本。因 此 ，额外的1（1−γ）2是需要一个公平的比较。整个状态-动作对。 我们用S来约束它。 此外，我们认为这是他们工作中的一个错误。|在他们的结果中被忽略了，|is missed in theirresult,+v：mala2255获取更多论文4.（1γ）42.（1γ）32є2.Σє2QINBO、AMRIT、MRIDUL、ALEC和 VANEET2. 相关工作无约束RL。近年来，强化学习在无约束表格环境中得到了很好的研究。基于算法的样本复杂度来比较不同的算法，该算法描述了实现最优策略所需的样本数量T。对于无限时域折扣奖励设置，Latterfly和Hutter（2012）修改了著名的基于模型的UCRL算法Jaksch等人（2010）以实现PACupperboundofO|S||一|在样品复合物上。 Li等人（2021）改进了−一种无模型变量Q-学习算法，用于测试样本复杂度O|S||一|. F或−情节设置与情节长度的H，阿扎尔等人。（2017）提出了基于模型的UCBVI算法，并给出了一个O-∞的样本复杂度H3|S||一|whi ch等于本文中给出的下限 沿着类似的路线，Jin et al. （2018）提出了一种无模型的UCBQ-校准方法，并对O-（H5）的样品络合物进行了分析。|S||一|）的。总之，在RL的无约束表格设置中存在许多接近最优的算法（基于模型的或无模型的）。基于模型的约束RL。 一旦估计的转移模型被给定或足够准确地估计，利用基于模型的算法来解决约束RL（CRL）问题就具有直观的意义，因为该问题归结为仅求解线性规划Altman（1999）。在基于模型的框架下，作者Efroni等人。（2020）提出了4种算法，即OptCMDP &OptCMDP-bonus，OptDual和OptPrimalDual，分别在原始，对偶和原始-对偶域中解决问题。 Brantley等人（2020）提出了一种模块化算法CONRL，该算法利用了乐观原则，可以应用于标准CRL设置，也可以扩展到凹凸和背包设置。 Kalagarla等人（2021）提出了UC-CFH算法，该算法也使用乐观原则，并为其算法提供了PAC分析。Ding等人（2021）考虑了具有约束设置的线性MDP，提出了OPDOP算法，并将其扩展到表格设置。无模型CRL。与基于模型的算法相比，无模型算法的现有结果较少。作者Achiam et al.（2017）提出了一种约束策略优化（CPO）算法，Tessler等人（2018）提出了奖励约束策略优化（RCPO）算法。作者Gattami et al. （2021）将CMDP与零和Markov-Bandit博弈联系起来，并为CMDP提供了有效的解决方案。然而，这些工作没有提供任何收敛速度的算法。此外，Ding et al. （2020）在表格和一般环境下提出了一个原始-对偶自然策略梯度算法，并提供了一个遗憾和约束违反分析。Xu等人提出了一种仅原始约束的修正策略优化（CRPO）算法。（2021）实现次线性收敛速度对约束违反的全局最优策略和次线性收敛速度也表1中总结了大多数具有特定样本复杂度和约束违反误差界的现有方法。最近，Chenet al. （2021）翻译将 约 束 RL 问 题 转 化 为 鞍 点 问 题 ， 提 出 了 一 种 原 对 偶 算 法 ， 该 算 法 具 有O<$（1/<$2）的采样复杂度，可获得最优的非线性可行解. 然而，该策略被认为是算法中的原始变量和估计+v：mala2255获取更多论文5Rt=0Gi不 不Gi0一种实现约束条件下的零约束条件的方法原始更新需要使用Q表，这增加了额外的样本复杂度和计算复杂度。在线约束凸优化。在带约束的标准在线凸优化领域中，近年来，Mahdavi et al.（2012）;Akhtar et al.（2021）进行了充分研究。最近，Akhtaret al. （2021）利用保守约束的思想来实现非线性-最优解具有O<$（1/<$2）的样本复杂度和零约束违反。我们利用保守的想法，在这项工作中，以更复杂的设置约束RL问题，以实现零约束违反。3. 问题公式化考虑一个由元组（S，A，P，r，gi，I，γ，ρ）定义的无限时域折扣报酬约束马尔可夫决策过程在该模型中，S表示有限状态空间（其中|S|状态数），A是有限动作空间（具有|一|动作数），且P：S ×A→N |S|给出了CMDP的过渡动力学（其中，D维中的概率单形 更具体地，P（|s，a）描述了以当前状态s和动作a为条件的下一状态的概率分布。我们表示P（s，J|s，a）为简单起见，作为Pa（s，sJ）。在CMDP元组中，r：S ×A→[0， 1]是奖励函数，gi：S ×A→[−1，1]是第i个约束成本函数，I表示约束的数量。此外，γ是折扣因子，ρ是状态的初始分布。无约束MDP问题总是存在一个确定性的最优策略然而，CMDP的最优策略可能是随机的。此外，（Altman，1999，定理3.1）表明考虑平稳随机策略就足够了。因此，让我们将平稳随机策略定义为π：S → π|一|，其将状态映射到动作空间中的分布。Chen等人给出了遵循这种策略π的报酬和约束成本的值函数。（ 2021年）Vπ（s）=（1−γ）Eπ∞γtr（st，at）<$，Vπ（s）=（1−γ）E∞γtgi（s，a），（1）对于所有的s∈ S。 在每个时刻t，对于给定的状态t和作用a t<$π（·|s t），下一个状态s t+1分布为s t+1<$P（·|s t，a t）。（1）中的期望是关于过渡的环境动态和随机策略π。 让我们把Jπ和Jπ记为期望值函数w.r.t.初始分布，如Jr，ρ（π）=Es<$ρ[Vπ（s0）]，rgi0Jgi，ρ（π）=ER[V π（s）]，（二更）这里的目标是在满足约束值函数的条件下，最大化关于策略π的奖励Jr，ρ（π）的期望值函数，公式为MaxπJr，ρ（π）（三）S.T. Jgi，ρ（π）≥ 0<$i ∈ [I]，t=0s0ρ+v：mala2255获取更多论文6. Σ−RGiΣQINBO、AMRIT、MRIDUL、ALEC和 VANEET其中[I]表示约束的索引。 我们注意到，在Eq. （3）优化在政策空间。然而，价值函数是关于政策的非线性函数。众所周知，（3）中的问题可以等价地写成：Altman（1999）在占有测度空间中的线性规划。因此，我们引入占用度量的概念如下。对于给定的策略π，占用度量定义为λ（s，a）=（1γ）∞t=0γtP（st=s，at=a），（4）其中s0<$ρ，a t<$π（·|s T），P（s t= s，a t= a）是在步骤t中访问状态s并采取动作a的概率。根据（4）中的定义，等式（1）中的值函数为：（3）可以表示为Esρ[Vπ（s）] =λ，rλ，Esρ [V π（s）]=. λ，giλ。（五）遵循（5）中的等价性，策略空间中的（3）的原始问题是等价的在由（Altman，1999，定理3.3（a）（b））给出的占用测度空间中，Maxλ≥0λ，rS.T. . λ，gi∈[I]≥0，一（六）A∈A（I−γPT）λa=（1−γ）ρ，其中λa= [λ（1，a），· · ·，λ（|S|，a）] ∈R| S|是λ的第a列。 请注意，Eq中的常数（6）求和为1，这意味着λ是有效的概率测度，并且我们定义Λ：={λ|s，aλ（s，a）= 1}作为概率单形。对于给定的占用度量λ，我们可以将策略πλ恢复为π λ（α|s）= 0λ（s，a）.（七）a′λ（s，AJ）由（Altman，1999，定理3.3（c））可知，如果λλ是方程中的问题的最优解，（6），则πλπ是方程中问题的最优策略。（三）、4. 算法开发在文献中充分研究了（3）中的问题，并且Ding et al. （2020）;Xu et al. （2021年）。所有现有的方法都能在满足O_∞（1/2）的约束条件下得到O_∞（1 /2）的目标最优间隙，其中R_∞是精度参数。 最近，Wei等人（2021）提出了一种三重Q算法实现零约束违反的成本，实现目标的最优性差距O<$（1/15）。这里的目标是开发一个算法，以一个chieve零约束违反，而不会遭受的目标最优性差距。为了做到这一点，我们认为保守的Akhtar等人提出的随机优化框架。（2021年），并利用它提出建议+v：mala2255获取更多论文7一.Σ≥∀ ∈一.Σ⟨⟩−−⟨⟩ΣLζΣ·−一种实现约束条件下的零约束条件的方法（6）中的约束MDP问题的保守版本为Maxλ≥0λ，rS.T.λ，giκ i[I]，（8b）<$（I−γPT）λa=（1−γ）ρ，（8c）a∈A其中κ >0是控制约束的保守性质的调谐参数。我们的想法是考虑（6）中原始不等式约束的更严格版本（由κ控制），这允许我们实现CMDPs的零约束违反，这不适用于任何现有算法。我们将在后面的收敛性分析部分中指定参数κ的具体值（参见秒5）。注意，方程中的问题的保守版本。 （8）仍然是LP，因此具有很强的二元性，这激励我们开发基于原始-对偶的算法来解决（8）中的问题。根据KKT定理，Eq. （8）等价于下面的鞍点问题，我们得到 通过将（8）的拉格朗日量写为L（λ，u，v）=λ，rλ+λi∈[ I]乌岛gi，λ+（1−γ）<$ρ，v<$+<$λT（γPa−I）v（9）a∈A=λ，r+u，GTλκ1+（1γ）ρ，v+<$λa，（γPa−I）v<$，（10）a∈A其中，u：= [u1，u2，· · ·，ui]T是与（8b）中的约束相对应的对偶变量的列向量，v是与（8c）中的等式约束相对应的对偶变量，G：= [g1，· · ·，gi]∈RS×A×I集合了（8b）中与I约束相对应的所有gi根据（10）中的拉格朗日量，等价鞍点问题由下式给出：maxmin（λ，u，v）。（十一）λ≥0 u≥0，v由于拉格朗日函数是线性的w.r.t.原始变量和对偶变量，已知鞍点可以由原始-对偶梯度方程Ned i′c和Ozdaglar（2009）求解。然而，由于我们假设过渡动力学P a是未知的，因此直接计算（11）中关于原始变量和对偶变量的拉格朗日梯度是不可能的。为了避免这个问题，我们求助于Wang（2020）提出的随机原始对偶方法，以无模型随机方式解决问题。我们假设存在一个生成模型，这是一个常见的假设在控制/RL应用。生成模型针对模型中的给定状态s和动作a产生下一个状态sj，并提供奖励r（s，a）来训练策略。为此，我们考虑S × A上的分布λ，以将（11）中的拉格朗日L（λ，u，v）的随机近似写为L（s，a，s′），s0（λ，u，v）（12）=（1−γ）v（s0）+1n（s，a）>0λ（s，a）Zsa（s，a）i∈[ I]kui，+v：mala2255获取更多论文8Σ′（s，a，[L··ζ-EQINBO、AMRIT、MRIDUL、ALEC和 VANEET哪里Zsa：=r（s，a）+γv（sJ）−v（s）+uigi（s，a），（13）i∈[ I]和s0<$p，当前状态动作对（s，a）<$p，以及下一状态sJ<$P（·|s，a）。我们注：随机近似L（12）中的（λ，u，v）是无偏估计，方程中的拉格朗日函数的tor（10）这意味着E×P（·|s，a），ρ（s，a，s′），s0]=L（λ，u，v），其中supp（λ）<$supp（λ）。我们可以把它看作是一个自适应的状态-动作对，这有助于控制随机梯度估计的方差。拉格朗日函数关于原始变量和对偶变量的随机梯度由下式给出：∇ˆλL（λ，u，v）=1n（s，a）>0ZsaMa）a，（十四）拉吉乌L（λ，u，v）=1n（s，a）>0λ（s，a）g（s，a）·（s，a）−κ1，（15）吉尔霍夫L（λ，u，v）=e（s0J）+1n（s，a）>0λ（s，a）（γe（sJ）−e（s）），（16）（s，a）其中我们定义e（s0J）=（1−γ）e（s0），其中e（s0）∈ R| S|是一个列向量，除了第s个元素等于1外，所有元素都等于0，|S| ×|一|是一个矩阵，只有（s，a）项等于1，所有其他项都是0，并且g（s，a）=[g1（s，a），···，gi（s，a）] T。我们注意到（14）中的M是用于收敛性分析的移位参数。所有的随机梯度的定义，我们现在准备提出的新算法称为保守随机原始对偶算法（CSPDA）总结在算法1。首先，我们在步骤1中初始化原始变量和对偶变量。在步骤4和5中，我们对（st，at，s0）进行采样，然后从生成模型中获得sJt。在步骤6中，我们通过梯度下降步骤和投影操作来更新对偶变量（关于U和V的定义，请参见引理1）。在第7步中，我们利用镜像上升更新并利用KL散度作为Bregman散度，以获得与Wang（2020）类似的对收敛速度分析的紧密依赖性。然后，对占用度量进行归一化，以使其保持有效分布。5. 收敛性分析在本节中，我们详细研究了所提出的算法1的收敛速度。我们从分析（11）中鞍点问题的对偶间隙开始。然后我们证明了算法1的输出对于CMDPs的对偶域优化问题（8）中的保守版本是最优的。最后，我们在政策空间进行了分析，并提出了这项工作的主要结果。我们证明了由最优约束测度λ也是最优的，同时也是零约束违背.在讨论收敛性分析之前，我们提供了本文工作所需的假设的详细描述·+v：mala2255获取更多论文93：−.t+λ=argmaxλ不一t=1不t=1不t=1一种实现约束条件下的零约束条件的方法约束条件下的1-C保守随机原边值问题算法RL输入：样本量T。初始分布ρ。贴现因子γ。参数：步长α、β。Slater变量，移位参数M，保守变量κ和常数δ∈（0，1）2输出：λ<$=1<$Tλt，u<$=1<$T ut和v<$=1<$Tvt1：初始化u1∈ U，v1∈ V且λ1=1·12：对于t = 1，2，...，没做λt：=（1δ）λt+δ1|St||一||一||A|4： 样本（st，at）和s0ρ5： 样本sJt|a t，s t），并观察奖励rsa6：将u和v的值函数更新为ut+1=uL（λt，ut，vt））（17）vt+1=vL（λt，ut，vt））（18）7：将占用计量更新为12λ1λL（λt，ut，vt），λ−λt<$不-βKL（λλ）（19）8：结束λt+1=λ12/λ12019年12月20日假设1（严格可行性）当reλε≥0时，re存在严格可行的可能性（8）求问题，.λ，gi−≥0<$i∈[I]（二十一）对于某些<0。且λa（I−γP）λa=（1−γ）ρT假设1是流行的斯莱特条件，这是经常需要在凸优化问题的分析更强的版本。Mahdavi et al.（2012）;Akhtar et al.（2021）也考虑了类似的假设，并且也有助于确保对偶变量的有界性（参见引理1）。我们注意到假设1是唯一的，利用保守约束的思想来获得零约束违反。长期.具体地说，假设1在证明（6）中的原始问题的最优目标值和（8）中的保守版本的最优目标值之间的距离是O（κ），如引理4所述。t+t++v：mala2255获取更多论文10ϕΣ4v|v-是的+的版本。wL（wt，λt），wt−w（二十三）1Tϕ1−γ（1−γ）πQINBO、AMRIT、MRIDUL、ALEC和 VANEET5.1 对偶缺口为了限制对偶差距，我们注意到鞍点算法的标准分析Ned ic和Ozdaglar（2009）;Akhtaretal. （2021）不适用，因为由于使用状态-动作对的自适应采样，更新中引入了无界噪声Wang（2020）;Zhang等人（2021）。因此，有必要获得梯度的显式界以及梯度的随机估计的方差。我们通过考虑假设1中斯莱特条件的形式开始分析引理1（有界对偶变量u和v）在假设1下，最优对偶变量uκ和vκκ1+二、a rebound e d. 通常，它认为，2并且，1−γ（1−γ）L.emma1在Ap ppendixC.1中提供。 因此，我们定义U：=。u|最大值1≤U和V，现在我们将（11）中的鞍点公式改写为maxminL（λ，u，v）。（二十二）λ∈Λ（u∈U，v∈V）在接下来的分析中，我们将处理（22）中的问题。首先，我们将引理2中的对偶间隙分解如下。引理2（对偶间隙）对于任何对偶变量u，v，让我们定义w=[uT，vT]T，并且考虑到u<$，v<$，λ<$如在Alxim1中定义的，对偶间隙可以被定义为L（u<$，v<$，λ<$κ）−L（u，v，λ<$）≤不t=1`（I）x`（I）x在引理9中提供了引理2的陈述中的项I和项II的界限和10（分别见附录C.4和C.5中的证明）。这有助于证明定理3中的主要结果，定理3建立了对偶间隙的最终界如下。定理3定义（u<$，v<$）：=argminu，vL（u，v，λ<$）. Reca llλεκ是保守Lagrange问题的最佳解。算法1的对偶间隙有界为：E[L（u<$，v<$，λ<$κ）−L（u<$，v<$，λ<$）]≤O. .我|S||一|1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 |S||一|）·1英寸。（二十四）T（1 −γ）V：=. 因为我们已经在数学上定义了+v：mala2255获取更多论文112ϕ一.Σ1−γ不ϕ（1−γ）π1−γE. λ<$，gi∈[I]，（26a）一种实现约束条件下的零约束条件的方法定理3的证明见附录C.3。定理3中的结果描述了对偶间隙对状态-作用空间基数的次线性依赖，直到对数因子。在下一小节中，我们利用对偶间隙上界分别推导出目标次优性和约束违反的上界5.2 双重目标和约束违反回想一下，方程中的鞍点问题。（22）是一个等价的问题，方程。（6）其中主要的差异是由于新引入的保守性参数κ。 因此，二元差距的收敛分析应该意味着方程中的占有测度的收敛。（ 八）、但在此之前，我们需要描述原始问题之间的差距（6）和（8）中的保守版本。下面的引理4表明，间隙的数量级为参数κ。引理4在假设1下，条件κ ≤ min {k，1}，原问题与保守问题的最优解之差为O（κ）。在数学上，它认为，<$λ，r<$−<$λκ，r<$≤κ。引理4的证明见附录D.1。 使用引理4的陈述和定理3，我们在下面的定理5中得到了关于输出占用测度的收敛结果。定理5F或任何0∈ 1，存在常数c∈1，使得如果T≥最大值16、42、1·c2I|S||一|1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 |S||一|）（二十五）ϵ21（1 −γ）22设κ=2c1。我|S||一|1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000|S||一|）且M=4[1+1+2]，则E<$（γPT−I）λ<$ a+（1−γ）ρ<$≤（1−γ）λ <$。（26 b）一此外，（6）的目标次优性由下式给出：E [<$λ<$，r<$−λ<$，r] ≤3 <$。（二十七）定理5的证明见附录D.2。接下来，我们介绍特殊情况以推论6的形式给出了定理5的等价结果（证明见附录D.3），它给出了无守恒参数κ= 0时的等价结果推论6（非零违规情况）设κ= 0。 对于任何一个大于0的，都存在一个常数c≠1，如果T≥c≠2·I|S||一|1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 |S||一|）则λ'满足constraintviolation，（6）中的原问题满足：1+v：mala2255获取更多论文12一E. λ<$，gi<$≥−i∈[I]（28a）1（1−γ）222E<$<$（γPT−I）λ<$a+（1−γ）ρ<$≤（1−γ）λ<$， （28 b）一子最优性由E [λ，r−]给出。λ<$，r] ≤λ。1+v：mala2255获取更多论文13−QINBO、AMRIT、MRIDUL、ALEC和 VANEET在（26 a）中，λ′是可行的（因此零约束违反）。另一方面，（28 a）中的下界是负的，这表明对偶空间中的约束对于λ′可能不满足。其次，我们展示了定理5中的结果如何有助于实现策略空间中的零约束违反。5.3 政策空间中的收敛分析我们已经建立了收敛的占用测度空间中的Sec。 5.2显示那就是，获得了一个最优的最优可行解，但要求零约束违反还不清楚 但在Eq中的一个小违规。（26 b）使λ′失去其物理意义，如（Zhang et al.，2021年，提案1）。因此，为了使这个想法更清晰，并明确地显示在这项工作中使用的保守思想的好处，我们进一步提出了在政策空间的结果。在Eq. 公式（26 b）提供了输出占用度量接近于最优度量的直觉，因此，导出的策略也应该接近于最优策略。这样的结果在数学上在定理7中给出。定理7（零违规）在定理5的条件下，由输出竞争机制得出的策略π<$是一个最优策略，并且达到零违规。从数学上讲，这意味着Jr，ρ（π<$）−E[Jr，ρ（π<$）]≤ε（29 a）E[Jgi，ρ（π<$）]≥0<$i∈[I].（29 b）定理7的证明见附录E.1。为了更好地理解定理7中结果的重要性，我们接下来给出推论8（见E. 2中的证明），它是定理7对于κ = 0的特殊情况。推论8（非零违反情形）在推论6的条件下，输出容量矩阵的引入策略π<$对于目标和约束都是一个非最优策略.更正式地说，Jr，ρ（π<$）−E[Jr，ρ（π<$）]≤ε（30 a）E [Jgi，ρ（π<$）]≥−i∈[I].（30 b）在比较（29 b）和（30 b）中的结果之后，利用守恒参数κ的益处变得清楚。6.一个可重构系统的评价在本节中，我们评估了离散时间中单服务器排队系统的算法1Altman（1999）[第5章]。在这个模型中，我们假设一个有限大小的缓冲区L。假设可能的到达发生在时隙的开始系统的状态是在时隙开始时在队列中等待的客户的数量，使得状态空间的大小为|S|= L + 1。我们假设有两种类型的动作：服务动作和流动作。服务动作选自[amin，amax]的有限子集A，使得0 0。总回报是（31）中的目标，约束值是L.H. S。在（31）中的约束。假设γ = 0。5，我们希望在同时满足服务和流量两个约束的情况下，最大化总的折扣累积奖励。因此，总体优化问题被给出为：minπa，πbE∞γt c（s，πa（s），πb（s））（31）S.T. E∞γt ci（s，πa（s），πb（s））<$≥0i = 1， 2t=0其中s0p、πa和πb分别是服务和流的策略。我们注意到，（31）中的期望是关于随机策略和+v：mala2255获取更多论文15QINBO、AMRIT、MRIDUL、ALEC和 VANEET转移概率对于模拟，我们选择L = 5，A = [0. 2，0。四，零。六，零。8，B = [0。四，零。五，零。六，零。对于除了状态s = L之外的所有状态，进一步地，我们选 择 Slater 变 量 n=0 。 2 ， 迭 代 次 数 T=100000 ， c_（ ？ ） 02 ， 并 选 择 conser vativevariableκ作为定理5的陈述。初始分布ρ设定为均匀分布。此外，成本函数被设置为c（s，a，b）=-s + 5，用于服务的约束函数被定义为c1（s，a，b）=-10a + 3，并且用于流的约束函数被定义为c2（s，a，b）=-8（1-b）2+ 1。2.我们运行200个独立的模拟，并收集平均值和标准方差。图1中，我们分别给出了当κ= 0和κ >0时，累积奖励和约束值的学习过程注意，图1中的y轴是在等式1中定义的累积奖励和约束函数。（31）. 可以看出，当κ >0时，约束值严格大于0，这与理论上的结果相匹配。此外，对于κ= 0和κ>0两者，奖励是相似的，而κ>0的情况有助于实现零约束违反。7. 结论本文研究了有限状态空间S和行动空间A下无限时域约束马尔可夫决策过程（CMDP）的最优策略学习问题。这个问题在文献中也被称为约束强化学习（CRL）。为了以无模型的方式解决该问题，我们基于Wang（2020）提出的随机化原始-对偶鞍点方法提出了一种新的保守随机原始-对偶算法（CSDPA）。 我们表明，要实现一个最优的策略，它是足够的运行所提出的算法1为|S||一|（|S||一|）的情况）（1−γ）222步此外，我们证明了所提出的算法1不违反任何I约束，这在CRL文献中是本作品所独有的。 我们的想法是考虑原始约束的保守版本（由参数κ控制），然后适当选择κ使我们能够使约束违反为零，同时仍然实现目标次优的最佳样本复杂度。+v：mala2255获取更多论文16Kr，1······（s）=r，1−−1γ概率为y1/K的π1（s）r，11r，11K一种实现约束条件下的零约束条件的方法通过原始-对偶方法实现约束强化学习的零约束违反的补充材料附录A. 表中参考文献之间的比较说明？？第一步：从白鹭到PAC结果表中列出了许多参考文献？？都是在情节设置中，并以后悔的形式给出结果，这被定义为<$Vr<$，1（s1）−Vπk（s1）≤f（H，|S|、|一|，T，δ），概率至少为1−δ（32）k=1其中T=KH。下面的方法提供了一个可能的近似正确（PAC）的结果，从遗憾。在学习范围K结束时，策略π<$可以被定义为如下：···· ··πk（s），概率为1/K概率为1/K的πK（s）（三十三）注意，对于k∈[K]，π<$c随机一致地使用差分多项式π k。我们，我们kn ow1<$KVπk（s1）=Vπ<$（s1）。 除以等式（32）