在本文中,我们在表格设置中建立了违法演员批评算法的全球最优性和收敛速度,而不使用密度比来校正行为政策的状态分布与目标政策之间的差异。我们的工作超出了现有的工作原理,最佳的策略梯度方法中的现有工作中使用确切的策略渐变来更新策略参数时,我们使用近似和随机更新步骤。我们的更新步骤不是渐变更新,因为我们不使用密度比以纠正状态分布,这与从业者做得好。我们的更新是近似的,因为我们使用学习的评论家而不是真正的价值函数。我们的更新是随机的,因为在每个步骤中,更新仅为当前状态操作对完成。此外,我们在分析中删除了现有作品的几个限制性假设。我们的工作中的核心是基于其均匀收缩性能的时源性Markov链中的通用随机近似算法的有限样本分析。
translated by 谷歌翻译
我们提出了一种新的多功能增强学习的新型政策梯度方法,其利用了两个不同的差异减少技术,并且不需要在迭代上进行大量批次。具体而言,我们提出了一种基于势头的分散策略梯度跟踪(MDPGT),其中使用新的基于动量的方差减少技术来接近具有重要性采样的本地策略梯度代理,并采用中间参数来跟踪两个连续的策略梯度代理。此外,MDPGT可证明$ \ mathcal {o}的最佳可用样本复杂性(n ^ { - 1} \ epsilon ^ {-3})$,用于汇聚到全球平均值的$ \ epsilon $ -stationary点n $本地性能函数(可能是非旋转)。这优于在分散的无模型增强学习中的最先进的样本复杂性,并且当用单个轨迹初始化时,采样复杂性与现有的分散的政策梯度方法获得的样本复杂性匹配。我们进一步验证了高斯策略函数的理论索赔。当所需的误差容忍$ \ epsilon $足够小时,MDPGT导致线性加速,以前已经在分散的随机优化中建立,但不是为了加强学习。最后,我们在多智能体增强学习基准环境下提供了实证结果,以支持我们的理论发现。
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 谷歌翻译
本文重点介绍了解决光滑非凸强凹入最小问题的随机方法,这导致了由于其深度学习中的潜在应用而受到越来越长的关注(例如,深度AUC最大化,分布鲁棒优化)。然而,大多数现有算法在实践中都很慢,并且它们的分析围绕到几乎静止点的收敛。我们考虑利用Polyak-\ L Ojasiewicz(PL)条件来设计更快的随机算法,具有更强的收敛保证。尽管已经用于设计许多随机最小化算法的PL条件,但它们对非凸敏最大优化的应用仍然罕见。在本文中,我们提出并分析了基于近端的跨越时代的方法的通用框架,许多众所周知的随机更新嵌入。以{\ BF原始物镜差和二元间隙}的方式建立快速收敛。与现有研究相比,(i)我们的分析基于一个新的Lyapunov函数,包括原始物理差距和正则化功能的二元间隙,(ii)结果更加全面,提高了更好的依赖性的速率不同假设下的条件号。我们还开展深层和非深度学习实验,以验证我们的方法的有效性。
translated by 谷歌翻译
使用悲观,推理缺乏详尽的勘探数据集时的脱机强化学习最近颇具知名度。尽管它增加了算法的鲁棒性,过于悲观的推理可以在排除利好政策的发现,这是流行的基于红利悲观的问题同样有害。在本文中,我们介绍一般函数近似的Bellman-一致悲观的概念:不是计算逐点下界的值的功能,我们在超过设定的与贝尔曼方程一致的功能的初始状态实现悲观。我们的理论保证只需要贝尔曼封闭性作为探索性的设置标准,其中基于奖金的情况下的悲观情绪未能提供担保。即使在线性函数逼近的特殊情况下更强的表现力假设成立,我们的结果由$ \ mathcal {}Ø(d)在其样品的复杂$在最近的基于奖金的方法改善的时候,动作的空间是有限的。值得注意的是,我们的算法,能够自动适应事后最好的偏差 - 方差折中,而大多数现有的方法中需要调整的额外超参数的先验。
translated by 谷歌翻译
提高样本效率是加固学习的长期目标。本文提出了$ \ mathtt {vrmpo} $算法:具有随机镜血液的样本高效策略梯度方法。在$ \ mathtt {vrmpo} $中,提出了一种新的差异减少的政策梯度估计,以提高样本效率。我们证明了所提出的$ \ mathtt {vrmpo} $只需要$ \ mathcal {o}(\ epsilon ^ {-3})$ at \ epsilon $ att \ epsilon $-uppryoge一阶静止点,符合策略优化的最佳样本复杂性。广泛的实验结果表明,$ \ mathtt {vrmpo} $胜过各种设置中最先进的政策梯度方法。
translated by 谷歌翻译
梯度下降上升(GDA),最简单的单环路算法用于非凸起最小化优化,广泛用于实际应用,例如生成的对抗网络(GANS)和对抗性训练。尽管其理想的简单性,最近的工作表明了理论上的GDA的较差收敛率,即使在一侧对象的强凹面也是如此。本文为两个替代的单环算法建立了新的收敛结果 - 交替GDA和平滑GDA - 在温和的假设下,目标对一个变量的polyak-lojasiewicz(pl)条件满足Polyak-lojasiewicz(pl)条件。我们证明,找到一个$ \ epsilon $ -stationary点,(i)交替的GDA及其随机变体(没有迷你批量),分别需要$ o(\ kappa ^ {2} \ epsilon ^ { - 2})$和$ o(\ kappa ^ {4} \ epsilon ^ {-4})$迭代,而(ii)平滑gda及其随机变体(没有迷你批次)分别需要$ o(\ kappa \ epsilon ^ { - 2}) $和$ o(\ kappa ^ {2} \ epsilon ^ { - 4})$迭代。后者大大改善了Vanilla GDA,并在类似的环境下给出了单环算法之间的最佳已知复杂性结果。我们进一步展示了这些算法在训练GAN和强大的非线性回归中的经验效率。
translated by 谷歌翻译
本文研究了协同多智能体增强学习(MARL)的分布式政策梯度,在通信网络上的代理人旨在找到最佳政策,以最大限度地提高所有代理人的当地返回的平均值。由于政策梯度的非凹形性能函数,用于凸面问题的现有分布式随机优化方法不能直接用于Marl中的政策梯度。本文提出了一种具有方差减少和渐变跟踪的分布式策略梯度,以解决政策梯度的高差,并利用重要的重量来解决采样过程中的非静止问题。然后,我们在平均平均固定间隙上提供一个上限,这取决于迭代的数量,迷你批量大小,秒钟大小,问题参数和网络拓扑。我们进一步建立了样本和通信复杂性,以获得$ \ epsilon $-upprymate静止点。对MARL控制问题的数值实验进行了验证了所提出算法的有效性。
translated by 谷歌翻译
政策优化,通过大规模优化技术最大化价值函数来学习兴趣的政策,位于现代强化学习(RL)的核心。除了价值最大化之外,其他实际考虑因素也出现,包括令人鼓舞的探索,以及确保由于安全,资源和运营限制而确保学习政策的某些结构性。这些考虑通常可以通过诉诸正规化的RL来占据,这增加了目标值函数,并通过结构促进正则化术语。专注于无限范围打折马尔可夫决策过程,本文提出了一种用于解决正规化的RL的广义策略镜血压(GPMD)算法。作为策略镜血压LAN的概括(2021),所提出的算法可以容纳一般类凸常规的常规阶级,以及在使用中的规则器的认识到的广泛的Bregman分歧。我们展示了我们的算法在整个学习速率范围内,以无维的方式在全球解决方案的整个学习速率范围内融合到全球解决方案,即使常规器缺乏强大的凸起和平滑度。此外,在不精确的策略评估和不完美的政策更新方面,该线性收敛特征是可透明的。提供数值实验以证实GPMD的适用性和吸引力性能。
translated by 谷歌翻译
我们研究马尔可夫决策过程(MDP)框架中的离线数据驱动的顺序决策问题。为了提高学习政策的概括性和适应性,我们建议通过一套关于在政策诱导的固定分配所在的分发的一套平均奖励来评估每项政策。给定由某些行为策略生成的多个轨迹的预收集数据集,我们的目标是在预先指定的策略类中学习一个强大的策略,可以最大化此集的最小值。利用半参数统计的理论,我们开发了一种统计上有效的策略学习方法,用于估算DE NED强大的最佳政策。在数据集中的总决策点方面建立了达到对数因子的速率最佳遗憾。
translated by 谷歌翻译
在本文中,我们考虑基于移动普通(SEMA)的广泛使用但不完全了解随机估计器,其仅需要{\ bf是一般无偏的随机oracle}。我们展示了Sema在一系列随机非凸优化问题上的力量。特别是,我们分析了基于SEMA的SEMA的{\ BF差异递归性能的各种随机方法(现有或新提出),即三个非凸优化,即标准随机非凸起最小化,随机非凸强烈凹入最小最大优化,随机均方优化。我们的贡献包括:(i)对于标准随机非凸起最小化,我们向亚当风格方法(包括ADAM,AMSGRAD,Adabound等)提供了一个简单而直观的融合证明,随着越来越大的“势头” “一阶时刻的参数,它给出了一种替代但更自然的方式来保证亚当融合; (ii)对于随机非凸强度凹入的最小值优化,我们介绍了一种基于移动平均估计器的单环原始 - 双随机动量和自适应方法,并确定其Oracle复杂性$ O(1 / \ epsilon ^ 4)$不使用大型批量大小,解决文献中的差距; (iii)对于随机双脚优化,我们介绍了一种基于移动平均估计器的单环随机方法,并确定其Oracle复杂性$ \ widetilde o(1 / \ epsilon ^ 4)$,而无需计算Hessian矩阵的SVD,改善最先进的结果。对于所有这些问题,我们还建立了使用随机梯度估计器的差异递减结果。
translated by 谷歌翻译
我们研究了随机游戏(SGS)的梯度播放算法的性能,其中每个代理商试图通过基于代理之间共享的当前状态信息来独立做出决策来最大限度地提高自己的总折扣奖励。通过在给定状态下选择某个动作的概率来直接参数化策略。我们展示了纳什均衡(NES)和一阶固定政策在此设置中等同,并在严格的NES周围给出局部收敛速度。此外,对于称为马尔可夫潜在游戏的SGS的子类(包括具有重要特殊情况的代理中具有相同奖励的协作设置),我们设计了一种基于样本的增强学习算法,并为两者提供非渐近全局收敛速度分析精确的梯度游戏和我们基于样本的学习算法。我们的结果表明,迭代的数量达到$ \ epsilon $ -Ne线性缩放,而不是指数级,而代理人数。还考虑了局部几何和局部稳定性,在那里我们证明严格的NE是总潜在功能的局部最大值,完全混合的NE是鞍点。
translated by 谷歌翻译
由于策略梯度定理导致的策略设置存在各种理论上 - 声音策略梯度算法,其为梯度提供了简化的形式。然而,由于存在多重目标和缺乏明确的脱助政策政策梯度定理,截止策略设置不太明确。在这项工作中,我们将这些目标统一到一个违规目标,并为此统一目标提供了政策梯度定理。推导涉及强调的权重和利息职能。我们显示多种策略来近似梯度,以识别权重(ACE)称为Actor评论家的算法。我们证明了以前(半梯度)脱离政策演员 - 评论家 - 特别是offpac和DPG - 收敛到错误的解决方案,而Ace找到最佳解决方案。我们还强调为什么这些半梯度方法仍然可以在实践中表现良好,表明ace中的方差策略。我们经验研究了两个经典控制环境的若干ACE变体和基于图像的环境,旨在说明每个梯度近似的权衡。我们发现,通过直接逼近强调权重,ACE在所有测试的所有设置中执行或优于offpac。
translated by 谷歌翻译
深度加强学习的最近成功的大部分是由正常化的政策优化(RPO)算法驱动,具有跨多个域的强大性能。在这家族的方法中,代理经过培训,以在惩罚某些引用或默认策略的行为中的偏差时最大化累积奖励。除了经验的成功外,还有一个强大的理论基础,了解应用于单一任务的RPO方法,与自然梯度,信任区域和变分方法有关。但是,对于多任务设置中的默认策略,对所需属性的正式理解有限,越来越重要的域作为现场转向培训更有能力的代理商。在这里,我们通过将默认策略的质量与其对优化的影响正式链接到其对其影响的效果方面,进行第一步才能填补这种差距。使用这些结果,我们将获得具有强大性能保证的多任务学习的原则性的RPO算法。
translated by 谷歌翻译
Q-Learning,旨在以无模式的方式学习Markov决策过程(MDP)的最佳Q函数,位于加强学习的核心。当涉及到同步设置时(从每次迭代中从生成模型中从生成模型中汲取独立样本)时,已经对理解Q学习的样本效率进行了实质性进展。考虑一个$ \ gamma $ -discounted infinite-horizo​​ n mdp与状态空间$ \ mathcal {s} $和动作空间$ \ mathcal {a} $:要产生一个entrywise $ \ varepsilon $ - 最佳q函数的克制,最先进的Q-Learning理论需要超出$ \ FRAC {| \ Mathcal {s} || \ mathcal {a} || \ {(1- \ gamma)^ 5 \ varepsilon的示例大小^ {2}} $,它无法匹配现有的最低限度下限。这引起了自然问题:Q-Learning的急剧性复杂性是什么?是Q-Learning可怕的次优吗?本文为同步设置解决了这些问题:(1)当$ | \ mathcal {a} | = 1 $(使q学习减少到TD学习)时,我们证明了TD学习的样本复杂性是最佳的最佳和尺度为$ \ frac {| \ mathcal {s} |} {(1- \ gamma)^ 3 \ varepsilon ^ 2} $(最多到日志系数); (2)当$ | \ mathcal {a} | \ geq 2 $时,我们解决了q-learning的样本复杂性,按$ \ frac {| \ mathcal {s} || \ mathcal {a} || } {(1- \ gamma)^ 4 \ varepsilon ^ 2} $(最多到日志系数)。我们的理论推出了Q-Leature的严格次优,当$ | \ mathcal {a} | \ geq 2 $,并严格严格估计在q-learning中的负面影响。最后,我们扩展了我们的分析以适应异步Q-Learning(即,与马尔可夫样本的情况),锐化其样本复杂性的地平线依赖性为$ \ frac {1} {(1- \ gamma)^ 4} $。
translated by 谷歌翻译
我们研究了在随机最短路径(SSP)设置中的学习问题,其中代理试图最小化在达到目标状态之前累积的预期成本。我们设计了一种新型基于模型的算法EB-SSP,仔细地偏离了经验转变,并通过探索奖励来赋予经验成本,以诱导乐观的SSP问题,其相关价值迭代方案被保证收敛。我们证明了EB-SSP实现了Minimax后悔率$ \ tilde {o}(b _ {\ star} \ sqrt {sak})$,其中$ k $是剧集的数量,$ s $是状态的数量, $ a $是行动的数量,而B _ {\ star} $绑定了从任何状态的最佳策略的预期累积成本,从而缩小了下限的差距。有趣的是,EB-SSP在没有参数的同时获得此结果,即,它不需要任何先前的$ B _ {\ star} $的知识,也不需要$ t _ {\ star} $,它绑定了预期的时间 ​​- 任何州的最佳政策的目标。此外,我们说明了各种情况(例如,当$ t _ {\ star} $的订单准确估计可用时,遗憾地仅包含对$ t _ {\ star} $的对数依赖性,因此产生超出有限范围MDP设置的第一个(几乎)的免地相会遗憾。
translated by 谷歌翻译
用于解决无约束光滑游戏的两个最突出的算法是经典随机梯度下降 - 上升(SGDA)和最近引入的随机共识优化(SCO)[Mescheder等,2017]。已知SGDA可以收敛到特定类别的游戏的静止点,但是当前的收敛分析需要有界方差假设。 SCO用于解决大规模对抗问题,但其收敛保证仅限于其确定性变体。在这项工作中,我们介绍了预期的共同胁迫条件,解释了它的好处,并在这种情况下提供了SGDA和SCO的第一次迭代收敛保证,以解决可能是非单调的一类随机变分不等式问题。我们将两种方法的线性会聚到解决方案的邻域时,当它们使用恒定的步长时,我们提出了富有识别的步骤化切换规则,以保证对确切解决方案的融合。此外,我们的收敛保证在任意抽样范式下担保,因此,我们对迷你匹配的复杂性进行了解。
translated by 谷歌翻译
我们研究了线性函数近似的政策评估问题,并且目前具有强烈的最优性保证的高效实用算法。我们首先通过证明在这个问题中建立基线的下限来建立基线和随机错误。特别是,我们在与转换内核的静止分布相关联的实例相关规范中证明了Oracle复杂性下限,并使用本地渐近最低限度机械在随机误差中证明依赖于随机误差的实例相关的下限IID观察模型。现有算法未能匹配这些下限中的至少一个:为了说明,我们分析了时间差异学习的方差减少变体,特别是它未能实现Oracle复杂性下限。为了解决这个问题,我们开发了加速,方差减少的快速时间差算法(VRFTD),其同时匹配两个下限,并达到实例 - 最优性的强烈概念。最后,我们将VRFTD算法扩展到Markovian观察的设置,并提供与I.I.D中的实例相关的收敛结果。设置到与链条的混合时间成比例的乘法因子。我们的理论保证最佳的最佳保证是通过数值实验证实的。
translated by 谷歌翻译
我们解决了加固学习的安全问题。我们在折扣无限地平线受限的Markov决策过程框架中提出了问题。现有结果表明,基于梯度的方法能够实现$ \ mathcal {o}(1 / \ sqrt {t})$全球收敛速度,用于最优差距和约束违规。我们展示了一种基于自然的基于政策梯度的算法,该算法具有更快的收敛速度$ \ mathcal {o}(\ log(t)/ t)$的最优性差距和约束违规。当满足Slater的条件并已知先验时,可以进一步保证足够大的$ T $的零限制违规,同时保持相同的收敛速度。
translated by 谷歌翻译
我们在$ \ Gamma $ -diScounted MDP中使用Polyak-Ruppert平均(A.K.A.,平均Q-Leaning)进行同步Q学习。我们为平均迭代$ \ bar {\ boldsymbol {q}}建立渐近常态。此外,我们展示$ \ bar {\ boldsymbol {q}} _ t $实际上是一个常规的渐近线性(RAL)估计值,用于最佳q-value函数$ \ boldsymbol {q} ^ * $与最有效的影响功能。它意味着平均Q学习迭代在所有RAL估算器之间具有最小的渐近方差。此外,我们为$ \ ell _ {\ infty} $错误$ \ mathbb {e} \ | \ | \ bar {\ boldsymbol {q}} _ t- \ boldsymbol {q} ^ *} ^ *} _ {\ idty} $,显示它与实例相关的下限以及最佳最低限度复杂性下限。作为一个副产品,我们发现Bellman噪音具有var-gaussian坐标,具有方差$ \ mathcal {o}((1- \ gamma)^ {-1})$而不是现行$ \ mathcal {o}((1- \ Gamma)^ { - 2})$根据标准界限奖励假设。子高斯结果有可能提高许多R1算法的样本复杂性。简而言之,我们的理论分析显示平均Q倾斜在统计上有效。
translated by 谷歌翻译