使用悲观,推理缺乏详尽的勘探数据集时的脱机强化学习最近颇具知名度。尽管它增加了算法的鲁棒性,过于悲观的推理可以在排除利好政策的发现,这是流行的基于红利悲观的问题同样有害。在本文中,我们介绍一般函数近似的Bellman-一致悲观的概念:不是计算逐点下界的值的功能,我们在超过设定的与贝尔曼方程一致的功能的初始状态实现悲观。我们的理论保证只需要贝尔曼封闭性作为探索性的设置标准,其中基于奖金的情况下的悲观情绪未能提供担保。即使在线性函数逼近的特殊情况下更强的表现力假设成立,我们的结果由$ \ mathcal {}Ø(d)在其样品的复杂$在最近的基于奖金的方法改善的时候,动作的空间是有限的。值得注意的是,我们的算法,能够自动适应事后最好的偏差 - 方差折中,而大多数现有的方法中需要调整的额外超参数的先验。
translated by 谷歌翻译
我们考虑在离线增强学习中有一个具有挑战性的理论问题(RL):仅在功能近似器的可靠性型假设下,通过缺乏足够覆盖的数据集获得样本效率保证。尽管现有的理论已经在可实现性和非探索数据下分别解决了学习,但没有工作能够同时解决这两者(除了我们对详细比较的并发工作除外)。在额外的差距假设下,我们根据边缘化重要性采样(MIS)形成的版本空间(MIS)为简单的悲观算法提供保证,并且保证只需要数据来涵盖最佳策略和功能类,以实现最佳价值和最佳价值和密度比函数。尽管在RL理论的其他领域中使用了类似的差距假设,但我们的工作是第一个识别离线RL中差距假设的实用性和新型机制,其功能近似较弱。
translated by 谷歌翻译
我们根据相对悲观主义的概念,在数据覆盖不足的情况下提出了经过对抗训练的演员评论家(ATAC),这是一种新的无模型算法(RL)。 ATAC被设计为两人Stackelberg游戏:政策演员与受对抗训练的价值评论家竞争,后者发现参与者不如数据收集行为策略的数据一致方案。我们证明,当演员在两人游戏中不后悔时,运行ATAC会产生一项政策,证明1)在控制悲观程度的各种超级参数上都超过了行为政策,而2)与最佳竞争。 policy covered by data with appropriately chosen hyperparameters.与现有作品相比,尤其是我们的框架提供了一般函数近似的理论保证,也提供了可扩展到复杂环境和大型数据集的深度RL实现。在D4RL基准测试中,ATAC在一系列连续的控制任务上始终优于最先进的离线RL算法。
translated by 谷歌翻译
低级MDP已成为研究强化学习中的表示和探索的重要模型。有了已知的代表,存在几种无模型的探索策略。相反,未知表示设置的所有算法都是基于模型的,因此需要对完整动力学进行建模。在这项工作中,我们介绍了低级MDP的第一个无模型表示学习算法。关键的算法贡献是一个新的Minimax表示学习目标,我们为其提供具有不同权衡的变体,其统计和计算属性不同。我们将这一表示的学习步骤与探索策略交织在一起,以无奖励的方式覆盖状态空间。所得算法可证明样品有效,并且可以适应一般函数近似以扩展到复杂的环境。
translated by 谷歌翻译
离线增强学习(RL)的样本效率保证通常依赖于对功能类别(例如Bellman-Completeness)和数据覆盖范围(例如,全政策浓缩性)的强有力的假设。尽管最近在放松这些假设方面做出了努力,但现有作品只能放松这两个因素之一,从而使另一个因素的强烈假设完好无损。作为一个重要的开放问题,我们是否可以实现对这两个因素的假设较弱的样本效率离线RL?在本文中,我们以积极的态度回答了这个问题。我们基于MDP的原始偶对偶进行分析了一种简单的算法,其中双重变量(打折占用)是使用密度比函数对离线数据进行建模的。通过适当的正则化,我们表明该算法仅在可变性和单极浓缩性下具有多项式样品的复杂性。我们还基于不同的假设提供了替代分析,以阐明离线RL原始二算法的性质。
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 谷歌翻译
我们研究马尔可夫决策过程(MDP)框架中的离线数据驱动的顺序决策问题。为了提高学习政策的概括性和适应性,我们建议通过一套关于在政策诱导的固定分配所在的分发的一套平均奖励来评估每项政策。给定由某些行为策略生成的多个轨迹的预收集数据集,我们的目标是在预先指定的策略类中学习一个强大的策略,可以最大化此集的最小值。利用半参数统计的理论,我们开发了一种统计上有效的策略学习方法,用于估算DE NED强大的最佳政策。在数据集中的总决策点方面建立了达到对数因子的速率最佳遗憾。
translated by 谷歌翻译
我们研究了用线性函数近似的加固学习中的违规评估(OPE)问题,旨在根据行为策略收集的脱机数据来估计目标策略的价值函数。我们建议纳入价值函数的方差信息以提高ope的样本效率。更具体地说,对于时间不均匀的epiSodic线性马尔可夫决策过程(MDP),我们提出了一种算法VA-OPE,它使用价值函数的估计方差重新重量拟合Q迭代中的Bellman残差。我们表明我们的算法达到了比最着名的结果绑定的更紧密的误差。我们还提供了行为政策与目标政策之间的分布转移的细粒度。广泛的数值实验证实了我们的理论。
translated by 谷歌翻译
我们在面对未衡量的混杂因素时研究离线增强学习(RL)。由于缺乏与环境的在线互动,离线RL面临以下两个重大挑战:(i)代理可能会被未观察到的状态变量混淆; (ii)提前收集的离线数据不能为环境提供足够的覆盖范围。为了应对上述挑战,我们借助工具变量研究了混杂的MDP中的政策学习。具体而言,我们首先建立了基于和边缘化的重要性采样(MIS)的识别结果,以确定混杂的MDP中的预期总奖励结果。然后,通过利用悲观主义和我们的认同结果,我们提出了各种政策学习方法,并具有有限样本的次级临时性保证,可以在最小的数据覆盖范围和建模假设下找到最佳的课堂政策。最后,我们广泛的理论研究和一项由肾脏移植动机的数值研究证明了该方法的有希望的表现。
translated by 谷歌翻译
强化学习(RL)的显着成功在很大程度上依赖于观察每个访问的州行动对的奖励。但是,在许多现实世界应用中,代理只能观察一个代表整个轨迹质量的分数,该分数称为{\ em轨迹方面的奖励}。在这种情况下,标准RL方法很难很好地利用轨迹的奖励,并且在政策评估中可能会产生巨大的偏见和方差错误。在这项工作中,我们提出了一种新颖的离线RL算法,称为悲观的价值迭代,奖励分解(分开),该算法将轨迹返回分解为每个步骤代理奖励,通过基于最小二乘的奖励重新分配,然后执行基于基于基于基于基于的价值迭代的迭代价值迭代的迭代迭代率关于博学的代理奖励。为了确保由分开构建的价值功能对最佳函数始终是悲观的,我们设计了一个新的罚款术语来抵消代理奖励的不确定性。对于具有较大状态空间的一般情节MDP,我们表明与过度参数化的神经网络函数近似近似能够实现$ \ tilde {\ Mathcal {o}}}(d _ {\ text {eff}}} h^2/\ sqrt {n}) $ suboftimality,其中$ h $是情节的长度,$ n $是样本总数,而$ d _ {\ text {eff}} $是神经切线核矩阵的有效维度。为了进一步说明结果,我们表明分开实现了$ \ tilde {\ mathcal {o}}}(dh^3/\ sqrt {n})$ subiptimation fi linearem mdps,其中$ d $是特征尺寸,匹配功能维度使用神经网络功能近似,当$ d _ {\ text {eff}} = dh $时。据我们所知,分开是第一种离线RL算法,在MDP总体上,轨迹奖励的效率非常有效。
translated by 谷歌翻译
We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic $Q$-Learning (VO$Q$L), based on $Q$-learning and bound its regret assuming completeness and bounded Eluder dimension for the regression function class. As a special case, VO$Q$L achieves $\tilde{O}(d\sqrt{HT}+d^6H^{5})$ regret over $T$ episodes for a horizon $H$ MDP under ($d$-dimensional) linear function approximation, which is asymptotically optimal. Our algorithm incorporates weighted regression-based upper and lower bounds on the optimal value function to obtain this improved regret. The algorithm is computationally efficient given a regression oracle over the function class, making this the first computationally tractable and statistically optimal approach for linear MDPs.
translated by 谷歌翻译
当我们不允许我们使用目标策略进行采样,而只能访问某些未知行为策略生成的数据集时,策略梯度(PG)估计就成为一个挑战。用于支付政策PG估计的常规方法通常会遭受明显的偏差或指数较大的差异。在本文中,我们提出了双拟合的PG估计(FPG)算法。假设访问Bellman-Complete值函数类,FPG可以与任意策略参数化一起工作。在线性值函数近似的情况下,我们在策略梯度估计误差上提供了一个紧密的有限样本上限,该界限受特征空间中测量的分布不匹配量的控制。我们还建立了FPG估计误差的渐近正态性,并具有精确的协方差表征,这进一步证明在统计上是最佳的,具有匹配的Cramer-Rao下限。从经验上讲,我们使用SoftMax表格或RELU策略网络评估FPG在策略梯度估计和策略优化方面的性能。在各种指标下,我们的结果表明,基于重要性采样和降低方差技术,FPG显着优于现有的非政策PG估计方法。
translated by 谷歌翻译
我们在无限地平线马尔可夫决策过程中考虑批量(离线)策略学习问题。通过移动健康应用程序的推动,我们专注于学习最大化长期平均奖励的政策。我们为平均奖励提出了一款双重强大估算器,并表明它实现了半导体效率。此外,我们开发了一种优化算法来计算参数化随机策略类中的最佳策略。估计政策的履行是通过政策阶级的最佳平均奖励与估计政策的平均奖励之间的差异来衡量,我们建立了有限样本的遗憾保证。通过模拟研究和促进体育活动的移动健康研究的分析来说明该方法的性能。
translated by 谷歌翻译
我们研究了离线加强学习(RL)的代表性学习,重点是离线政策评估(OPE)的重要任务。最近的工作表明,与监督的学习相反,Q功能的可实现性不足以学习。样品效率OPE的两个足够条件是Bellman的完整性和覆盖范围。先前的工作通常假设给出满足这些条件的表示形式,结果大多是理论上的。在这项工作中,我们提出了BCRL,该BCRL直接从数据中吸取了近似线性的贝尔曼完整表示,并具有良好的覆盖范围。通过这种学识渊博的表示,我们使用最小平方策略评估(LSPE)执行OPE,并在我们学习的表示中具有线性函数。我们提出了端到端的理论分析,表明我们的两阶段算法享有多项式样本复杂性,该算法在所考虑的丰富类别中提供了一些表示形式,这是线性的贝尔曼完成。从经验上讲,我们广泛评估了我们的DeepMind Control Suite的具有挑战性的基于图像的连续控制任务。我们显示我们的表示能够与针对非政策RL开发的先前表示的学习方法(例如Curl,SPR)相比,可以更好地使用OPE。 BCRL使用最先进的方法拟合Q评估(FQE)实现竞争性OPE误差,并在评估超出初始状态分布的评估时击败FQE。我们的消融表明,我们方法的线性铃铛完整和覆盖范围都至关重要。
translated by 谷歌翻译
Modern Reinforcement Learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational and statistical efficiency, especially given the need to manage the exploration/exploitation tradeoff. As a result, a core RL question remains open: how can we design provably efficient RL algorithms that incorporate function approximation? This question persists even in a basic setting with linear dynamics and linear rewards, for which only linear function approximation is needed.This paper presents the first provable RL algorithm with both polynomial runtime and polynomial sample complexity in this linear setting, without requiring a "simulator" or additional assumptions. Concretely, we prove that an optimistic modification of Least-Squares Value Iteration (LSVI)-a classical algorithm frequently studied in the linear setting-achieves O( √ d 3 H 3 T ) regret, where d is the ambient dimension of feature space, H is the length of each episode, and T is the total number of steps. Importantly, such regret is independent of the number of states and actions.
translated by 谷歌翻译
获取一阶遗憾界限 - 遗憾的界限不是作为最坏情况,但有一些衡量给定实例的最佳政策的性能 - 是连续决策的核心问题。虽然这种界限存在于许多设置中,但它们在具有大状态空间的钢筋学习中被证明是难以捉摸的。在这项工作中,我们解决了这个差距,并表明可以将遗憾的缩放作为$ \ mathcal {o}(\ sqrt {v_1 ^ \ star})$中的钢筋学习,即用大状态空间,即线性MDP设置。这里$ v_1 ^ \ star $是最佳政策的价值,$ k $是剧集的数量。我们证明基于最小二乘估计的现有技术不足以获得该结果,而是基于强大的Catoni平均估计器制定一种新的稳健自归一化浓度,其可能具有独立兴趣。
translated by 谷歌翻译
随着代表性学习成为一种在实践中降低增强学习(RL)样本复杂性(RL)的强大技术,对其优势的理论理解仍然是有限的。在本文中,我们从理论上表征了在低级马尔可夫决策过程(MDP)模型下表示学习的好处。我们首先研究多任务低级RL(作为上游培训),所有任务都共享一个共同的表示,并提出了一种称为加油的新型多任务奖励算法。加油站同时了解每个任务的过渡内核和近乎最佳的策略,并为下游任务输出良好的代表。我们的结果表明,只要任务总数高于一定的阈值,多任务表示学习比单独学习的样本效率要高。然后,我们研究在线和离线设置中的下游RL,在该设置中,代理商分配了一个新任务,共享与上游任务相同的表示形式。对于在线和离线设置,我们都会开发出样本效率高的算法,并表明它找到了一个近乎最佳的策略,其次要差距在上游中学习的估计误差和一个消失的术语作为数字作为数字的估计误差的范围。下游样品的大量变大。我们在线和离线RL的下游结果进一步捕获了从上游采用学习的表示形式的好处,而不是直接学习低级模型的表示。据我们所知,这是第一个理论研究,它表征了代表性学习在基于探索的无奖励多任务RL中对上游和下游任务的好处。
translated by 谷歌翻译
我们在使用函数近似的情况下,在使用最小的Minimax方法估算这些功能时,使用功能近似来实现函数近似和$ q $ functions的理论表征。在各种可靠性和完整性假设的组合下,我们表明Minimax方法使我们能够实现重量和质量功能的快速收敛速度,其特征在于关键的不平等\ citep {bartlett2005}。基于此结果,我们分析了OPE的收敛速率。特别是,我们引入了新型的替代完整性条件,在该条件下,OPE是可行的,我们在非尾部环境中以一阶效率提出了第一个有限样本结果,即在领先期限中具有最小的系数。
translated by 谷歌翻译
This paper studies systematic exploration for reinforcement learning with rich observations and function approximation. We introduce a new model called contextual decision processes, that unifies and generalizes most prior settings. Our first contribution is a complexity measure, the Bellman rank , that we show enables tractable learning of near-optimal behavior in these processes and is naturally small for many well-studied reinforcement learning settings. Our second contribution is a new reinforcement learning algorithm that engages in systematic exploration to learn contextual decision processes with low Bellman rank. Our algorithm provably learns near-optimal behavior with a number of samples that is polynomial in all relevant parameters but independent of the number of unique observations. The approach uses Bellman error minimization with optimistic exploration and provides new insights into efficient exploration for reinforcement learning with function approximation.
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 谷歌翻译