深度加强学习的最近成功的大部分是由正常化的政策优化(RPO)算法驱动,具有跨多个域的强大性能。在这家族的方法中,代理经过培训,以在惩罚某些引用或默认策略的行为中的偏差时最大化累积奖励。除了经验的成功外,还有一个强大的理论基础,了解应用于单一任务的RPO方法,与自然梯度,信任区域和变分方法有关。但是,对于多任务设置中的默认策略,对所需属性的正式理解有限,越来越重要的域作为现场转向培训更有能力的代理商。在这里,我们通过将默认策略的质量与其对优化的影响正式链接到其对其影响的效果方面,进行第一步才能填补这种差距。使用这些结果,我们将获得具有强大性能保证的多任务学习的原则性的RPO算法。
translated by 谷歌翻译
我们提出了一个基于最小描述长度(MDL)原理的多任务加固学习的新颖框架。在我们称MDL-Control(MDL-C)的这种方法中,代理商在面临的任务中学习了共同的结构,然后将其提炼成更简单的表示,从而促进更快的收敛性和对新任务的概括。这样一来,MDL-C自然将适应性适应与任务分布的认知不确定性平衡。我们通过MDL原理与贝叶斯推论之间的正式联系来激励MDL-C,得出理论性能保证,并在离散和高维连续控制任务上证明了MDL-C的经验有效性。从经验上讲,该框架用于修改现有的策略优化方法,并在离散和高维连续控制问题中改善其多任务性能。
translated by 谷歌翻译
策略梯度方法适用于复杂的,不理解的,通过对参数化的策略进行随机梯度下降来控制问题。不幸的是,即使对于可以通过标准动态编程技术解决的简单控制问题,策略梯度算法也会面临非凸优化问题,并且被广泛理解为仅收敛到固定点。这项工作确定了结构属性 - 通过几个经典控制问题共享 - 确保策略梯度目标函数尽管是非凸面,但没有次优的固定点。当这些条件得到加强时,该目标满足了产生收敛速率的Polyak-lojasiewicz(梯度优势)条件。当其中一些条件放松时,我们还可以在任何固定点的最佳差距上提供界限。
translated by 谷歌翻译
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.
translated by 谷歌翻译
政策优化,通过大规模优化技术最大化价值函数来学习兴趣的政策,位于现代强化学习(RL)的核心。除了价值最大化之外,其他实际考虑因素也出现,包括令人鼓舞的探索,以及确保由于安全,资源和运营限制而确保学习政策的某些结构性。这些考虑通常可以通过诉诸正规化的RL来占据,这增加了目标值函数,并通过结构促进正则化术语。专注于无限范围打折马尔可夫决策过程,本文提出了一种用于解决正规化的RL的广义策略镜血压(GPMD)算法。作为策略镜血压LAN的概括(2021),所提出的算法可以容纳一般类凸常规的常规阶级,以及在使用中的规则器的认识到的广泛的Bregman分歧。我们展示了我们的算法在整个学习速率范围内,以无维的方式在全球解决方案的整个学习速率范围内融合到全球解决方案,即使常规器缺乏强大的凸起和平滑度。此外,在不精确的策略评估和不完美的政策更新方面,该线性收敛特征是可透明的。提供数值实验以证实GPMD的适用性和吸引力性能。
translated by 谷歌翻译
我们重新审视了最简单的设置之一中的政策梯度方法的有限时间分析:有限状态和动作MDP,具有由所有随机策略组成的策略类和精确的渐变评估。有一些最近的工作将此设置视为平滑的非线性优化问题的实例,并显示具有小阶梯大小的子线性收敛速率。在这里,我们根据与政策迭代的连接采取不同的透视,并显示政策梯度方法的许多变体成功,阶梯大小大,并达到了线性收敛速率。
translated by 谷歌翻译
Epsilon-Greedy,SoftMax或Gaussian噪声等近视探索政策在某些强化学习任务中无法有效探索,但是在许多其他方面,它们的表现都很好。实际上,实际上,由于简单性,它们通常被选为最佳选择。但是,对于哪些任务执行此类政策成功?我们可以为他们的有利表现提供理论保证吗?尽管这些政策具有显着的实际重要性,但这些关键问题几乎没有得到研究。本文介绍了对此类政策的理论分析,并为通过近视探索提供了对增强学习的首次遗憾和样本复杂性。我们的结果适用于具有有限的Bellman Eluder维度的情节MDP中的基于价值功能的算法。我们提出了一种新的复杂度度量,称为近视探索差距,用Alpha表示,该差距捕获了MDP的结构属性,勘探策略和给定的值函数类别。我们表明,近视探索的样品复杂性与该数量的倒数1 / alpha^2二次地量表。我们通过具体的例子进一步证明,由于相应的动态和奖励结构,在近视探索成功的几项任务中,近视探索差距确实是有利的。
translated by 谷歌翻译
我们研究具有多个奖励价值函数的马尔可夫决策过程(MDP)的政策优化,应根据给定的标准共同优化,例如比例公平(平滑凹面标量),硬约束(约束MDP)和Max-Min Trade-离开。我们提出了一个改变锚定的正规自然政策梯度(ARNPG)框架,该框架可以系统地将良好表现的一阶方法中的思想纳入多目标MDP问题的策略优化算法的设计。从理论上讲,基于ARNPG框架的设计算法实现了$ \ tilde {o}(1/t)$全局收敛,并具有精确的梯度。从经验上讲,与某些现有的基于策略梯度的方法相比,ARNPG引导的算法在精确梯度和基于样本的场景中也表现出卓越的性能。
translated by 谷歌翻译
政策梯度(PG)算法是备受期待的强化学习对现实世界控制任务(例如机器人技术)的最佳候选人之一。但是,每当必须在物理系统上执行学习过程本身或涉及任何形式的人类计算机相互作用时,这些方法的反复试验性质就会提出安全问题。在本文中,我们解决了一种特定的安全公式,其中目标和危险都以标量奖励信号进行编码,并且学习代理被限制为从不恶化其性能,以衡量为预期的奖励总和。通过从随机优化的角度研究仅行为者的政策梯度,我们为广泛的参数政策建立了改进保证,从而将现有结果推广到高斯政策上。这与策略梯度估计器的差异的新型上限一起,使我们能够识别出具有很高概率的单调改进的元参数计划。两个关键的元参数是参数更新的步长和梯度估计的批处理大小。通过对这些元参数的联合自适应选择,我们获得了具有单调改进保证的政策梯度算法。
translated by 谷歌翻译
在许多顺序决策问题(例如,机器人控制,游戏播放,顺序预测),人类或专家数据可用包含有关任务的有用信息。然而,来自少量专家数据的模仿学习(IL)可能在具有复杂动态的高维环境中具有挑战性。行为克隆是一种简单的方法,由于其简单的实现和稳定的收敛而被广泛使用,但不利用涉及环境动态的任何信息。由于对奖励和政策近似器或偏差,高方差梯度估计器,难以在实践中难以在实践中努力训练的许多现有方法。我们介绍了一种用于动态感知IL的方法,它通过学习单个Q函数来避免对抗训练,隐含地代表奖励和策略。在标准基准测试中,隐式学习的奖励显示与地面真实奖励的高正面相关性,说明我们的方法也可以用于逆钢筋学习(IRL)。我们的方法,逆软Q学习(IQ-Learn)获得了最先进的结果,在离线和在线模仿学习设置中,显着优于现有的现有方法,这些方法都在所需的环境交互和高维空间中的可扩展性中,通常超过3倍。
translated by 谷歌翻译
政策优化是设计强化学习算法的基本原则,一个例子是具有剪切的替代物镜(PPO-CLIP)的近端政策优化算法(PPO-CLIP),由于其简单性和有效性,该算法已被普遍用于深度强化学习。尽管具有出色的经验表现,但PPO-CLIP尚未通过最新的理论证明是合理的。在本文中,我们在神经功能近似下建立了PPO-CLIP的第一个全局收敛速率。我们确定分析PPO-CLIP的基本挑战并用两个核心思想解决:(i)我们从铰链损失的角度重新解释了PPO-CLIP,这将政策改进与解决铰链损失和铰链损失和铰链损失和铰链分类问题的联系联系起来。提供PPO-CLIP目标的广义版。 (ii)基于上面的观点,我们提出了一个两步的策略改进方案,该方案通过熵镜下降和基于回归的策略更新方案从复杂的神经策略参数借助复杂的神经策略参数化来促进收敛分析。此外,我们的理论结果提供了剪辑机理对PPO-CLIP收敛的影响的首次表征。通过实验,我们从经验上验证了PPO-CLIP的重新解释,并在各种RL基准任务上具有各种分类器的广义目标。
translated by 谷歌翻译
For many applications of reinforcement learning it can be more convenient to specify both a reward function and constraints, rather than trying to design behavior through the reward function. For example, systems that physically interact with or around humans should satisfy safety constraints. Recent advances in policy search algorithms (
translated by 谷歌翻译
Reinforcement learning (RL) problems can be challenging without well-shaped rewards. Prior work on provably efficient RL methods generally proposes to address this issue with dedicated exploration strategies. However, another way to tackle this challenge is to reformulate it as a multi-task RL problem, where the task space contains not only the challenging task of interest but also easier tasks that implicitly function as a curriculum. Such a reformulation opens up the possibility of running existing multi-task RL methods as a more efficient alternative to solving a single challenging task from scratch. In this work, we provide a theoretical framework that reformulates a single-task RL problem as a multi-task RL problem defined by a curriculum. Under mild regularity conditions on the curriculum, we show that sequentially solving each task in the multi-task RL problem is more computationally efficient than solving the original single-task problem, without any explicit exploration bonuses or other exploration strategies. We also show that our theoretical insights can be translated into an effective practical learning algorithm that can accelerate curriculum learning on simulated robotic tasks.
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 谷歌翻译
民间传说表明,政策梯度比其相对,近似政策迭代更为强大。本文研究了国家聚集表示的案例,该案例是对状态空间进行分区的情况,并且在分区上保持了策略或价值函数近似。本文显示了一种策略梯度方法收敛到政策,该政策的遗憾是由$ \ epsilon $界定的,这是属于公共分区的国家行动值函数的两个要素之间的最大区别。通过相同的表示,近似政策迭代和近似价值迭代都可以产生政策,其遗憾的比例为$ \ epsilon/(1- \ gamma)$,其中$ \ gamma $是折扣因子。面对固有的近似误差,局部优化真实决策目标的方法可以更加健壮。
translated by 谷歌翻译
离线增强学习(RL)的样本效率保证通常依赖于对功能类别(例如Bellman-Completeness)和数据覆盖范围(例如,全政策浓缩性)的强有力的假设。尽管最近在放松这些假设方面做出了努力,但现有作品只能放松这两个因素之一,从而使另一个因素的强烈假设完好无损。作为一个重要的开放问题,我们是否可以实现对这两个因素的假设较弱的样本效率离线RL?在本文中,我们以积极的态度回答了这个问题。我们基于MDP的原始偶对偶进行分析了一种简单的算法,其中双重变量(打折占用)是使用密度比函数对离线数据进行建模的。通过适当的正则化,我们表明该算法仅在可变性和单极浓缩性下具有多项式样品的复杂性。我们还基于不同的假设提供了替代分析,以阐明离线RL原始二算法的性质。
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 谷歌翻译
在本文中,我们提出了一种新的策略梯度(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问题提供了新的观点。
translated by 谷歌翻译
尽管在理解增强学习的最小样本复杂性(RL)(在“最坏情况”的实例上学习的复杂性)方面已经取得了很多进展,但这种复杂性的衡量标准通常不会捕捉到真正的学习困难。在实践中,在“简单”的情况下,我们可能希望获得比最糟糕的实例可以实现的要好得多。在这项工作中,我们试图理解在具有线性函数近似的RL设置中学习近乎最佳策略(PAC RL)的“实例依赖性”复杂性。我们提出了一种算法,\ textsc {pedel},该算法实现了依赖于实例的复杂性的量度,这是RL中的第一个具有功能近似设置,从而捕获了每个特定问题实例的学习难度。通过一个明确的示例,我们表明\ textsc {pedel}可以在低重晶,最小值 - 最佳算法上获得可证明的收益,并且这种算法无法达到实例 - 最佳速率。我们的方法取决于基于设计的新型实验程序,该程序将勘探预算重点放在与学习近乎最佳政策最相关的“方向”上,并且可能具有独立的兴趣。
translated by 谷歌翻译
Effectively leveraging large, previously collected datasets in reinforcement learning (RL) is a key challenge for large-scale real-world applications. Offline RL algorithms promise to learn effective policies from previously-collected, static datasets without further interaction. However, in practice, offline RL presents a major challenge, and standard off-policy RL methods can fail due to overestimation of values induced by the distributional shift between the dataset and the learned policy, especially when training on complex and multi-modal data distributions. In this paper, we propose conservative Q-learning (CQL), which aims to address these limitations by learning a conservative Q-function such that the expected value of a policy under this Q-function lower-bounds its true value. We theoretically show that CQL produces a lower bound on the value of the current policy and that it can be incorporated into a policy learning procedure with theoretical improvement guarantees. In practice, CQL augments the standard Bellman error objective with a simple Q-value regularizer which is straightforward to implement on top of existing deep Q-learning and actor-critic implementations. On both discrete and continuous control domains, we show that CQL substantially outperforms existing offline RL methods, often learning policies that attain 2-5 times higher final return, especially when learning from complex and multi-modal data distributions.Preprint. Under review.
translated by 谷歌翻译