随着代表性学习成为一种在实践中降低增强学习(RL)样本复杂性(RL)的强大技术,对其优势的理论理解仍然是有限的。在本文中,我们从理论上表征了在低级马尔可夫决策过程(MDP)模型下表示学习的好处。我们首先研究多任务低级RL(作为上游培训),所有任务都共享一个共同的表示,并提出了一种称为加油的新型多任务奖励算法。加油站同时了解每个任务的过渡内核和近乎最佳的策略,并为下游任务输出良好的代表。我们的结果表明,只要任务总数高于一定的阈值,多任务表示学习比单独学习的样本效率要高。然后,我们研究在线和离线设置中的下游RL,在该设置中,代理商分配了一个新任务,共享与上游任务相同的表示形式。对于在线和离线设置,我们都会开发出样本效率高的算法,并表明它找到了一个近乎最佳的策略,其次要差距在上游中学习的估计误差和一个消失的术语作为数字作为数字的估计误差的范围。下游样品的大量变大。我们在线和离线RL的下游结果进一步捕获了从上游采用学习的表示形式的好处,而不是直接学习低级模型的表示。据我们所知,这是第一个理论研究,它表征了代表性学习在基于探索的无奖励多任务RL中对上游和下游任务的好处。
translated by 谷歌翻译
这项工作研究了RL中的代表性学习问题:我们如何学习紧凑的低维表示,使得在代表之上,我们可以以示例有效的方式执行诸如勘探和开发的RL程序。我们专注于低级马尔可夫决策过程(MDP),其中转换动态对应于低秩转换矩阵。与假设表示的事先作品(例如,线性MDP)不同,这里我们需要学习低秩MDP的表示。我们研究在线RL和离线RL设置。对于在线设置,在Flambe(Agarwal et.al)中使用相同的计算oracells操作,用于在低级MDP中学习表示的最先进的算法,我们提出了一种算法Rep-UCB上部置信束缚的驱动表示学习对于RL),这显着提高了$ \ widetilde {o}的样本复杂性(a ^ 9 d ^ 7 /(\ epsilon ^ {10}(1- \ gamma)^ {22}),因为flambe到$ \ widetilde {o}(a ^ 4 d ^ 4 /(\ epsilon ^ 2(1- \ gamma)^ {3})$ d $是转换矩阵的等级(或地面真相表示的维度) ,$ a $是行动次数,而$ \ gamma $是折扣因素。值得注意的是,rep-ucb比flambe更简单,因为它直接余额余额表示学习,探索和剥削之间的相互作用,而Flambe是一种探索的探索式风格方法,并且必须逐步执行无奖励探索及时。对于离线RL设置,我们开发了一种利用悲观主义在部分覆盖条件下学习的算法:我们的算法能够与脱机分布所涵盖的策略进行竞争。
translated by 谷歌翻译
尽管无奖励强化学习勘探阶段的主要目标(RF-RL)是减少具有最小轨迹数量的估计模型中的不确定性时间。目前尚不清楚这种安全的探索要求如何影响相应的样本复杂性,以实现所获得的计划中所需的最佳性。在这项工作中,我们首次尝试回答这个问题。特别是,我们考虑了事先知道安全基线政策的情况,并提出了一个统一的安全奖励探索(甜蜜)框架。然后,我们将甜蜜框架专门为表格和低级MDP设置,并分别开发出算法所构成的表格甜味和低级别甜味。两种算法都利用了新引入的截短值函数的凹度和连续性,并保证在探索过程中以高概率侵犯了零约束。此外,两种算法都可以在计划阶段的任何约束中找到近乎最佳的政策。值得注意的是,算法下的样本复杂性在无限制的对应物中匹配甚至超过最恒定因素的最新情况,这证明安全约束几乎不会增加RF-RL的样本复杂性。
translated by 谷歌翻译
低级MDP已成为研究强化学习中的表示和探索的重要模型。有了已知的代表,存在几种无模型的探索策略。相反,未知表示设置的所有算法都是基于模型的,因此需要对完整动力学进行建模。在这项工作中,我们介绍了低级MDP的第一个无模型表示学习算法。关键的算法贡献是一个新的Minimax表示学习目标,我们为其提供具有不同权衡的变体,其统计和计算属性不同。我们将这一表示的学习步骤与探索策略交织在一起,以无奖励的方式覆盖状态空间。所得算法可证明样品有效,并且可以适应一般函数近似以扩展到复杂的环境。
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 谷歌翻译
我们研究了基于模型的无奖励加强学习,具有ePiSodic Markov决策过程的线性函数近似(MDP)。在此设置中,代理在两个阶段工作。在勘探阶段,代理商与环境相互作用并在没有奖励的情况下收集样品。在规划阶段,代理商给出了特定的奖励功能,并使用从勘探阶段收集的样品来学习良好的政策。我们提出了一种新的可直接有效的算法,称为UCRL-RFE在线性混合MDP假设,其中MDP的转换概率内核可以通过线性函数参数化,在状态,动作和下一个状态的三联体上定义的某些特征映射上参数化。我们展示了获得$ \ epsilon $-Optimal策略进行任意奖励函数,Ucrl-RFE需要以大多数$ \ tilde {\ mathcal {o}}来进行采样(h ^ 5d ^ 2 \ epsilon ^ { - 2})勘探阶段期间的$派对。在这里,$ H $是集的长度,$ d $是特征映射的尺寸。我们还使用Bernstein型奖金提出了一种UCRL-RFE的变种,并表明它需要在大多数$ \ TINDE {\ MATHCAL {o}}(H ^ 4D(H + D)\ epsilon ^ { - 2})进行样本$达到$ \ epsilon $ -optimal政策。通过构建特殊类的线性混合MDPS,我们还证明了对于任何无奖励算法,它需要至少为$ \ TINDE \ OMEGA(H ^ 2d \ epsilon ^ { - 2})$剧集来获取$ \ epsilon $ -optimal政策。我们的上限与依赖于$ \ epsilon $的依赖性和$ d $ if $ h \ ge d $。
translated by 谷歌翻译
我们研究了用线性函数近似的加固学习中的违规评估(OPE)问题,旨在根据行为策略收集的脱机数据来估计目标策略的价值函数。我们建议纳入价值函数的方差信息以提高ope的样本效率。更具体地说,对于时间不均匀的epiSodic线性马尔可夫决策过程(MDP),我们提出了一种算法VA-OPE,它使用价值函数的估计方差重新重量拟合Q迭代中的Bellman残差。我们表明我们的算法达到了比最着名的结果绑定的更紧密的误差。我们还提供了行为政策与目标政策之间的分布转移的细粒度。广泛的数值实验证实了我们的理论。
translated by 谷歌翻译
We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making, which includes Markov decision process (MDP), partially observable Markov decision process (POMDP), and predictive state representation (PSR) as special cases. Toward finding the minimum assumption that empowers sample efficient learning, we propose a novel complexity measure, generalized eluder coefficient (GEC), which characterizes the fundamental tradeoff between exploration and exploitation in online interactive decision making. In specific, GEC captures the hardness of exploration by comparing the error of predicting the performance of the updated policy with the in-sample training error evaluated on the historical data. We show that RL problems with low GEC form a remarkably rich class, which subsumes low Bellman eluder dimension problems, bilinear class, low witness rank problems, PO-bilinear class, and generalized regular PSR, where generalized regular PSR, a new tractable PSR class identified by us, includes nearly all known tractable POMDPs. Furthermore, in terms of algorithm design, we propose a generic posterior sampling algorithm, which can be implemented in both model-free and model-based fashion, under both fully observable and partially observable settings. The proposed algorithm modifies the standard posterior sampling algorithm in two aspects: (i) we use an optimistic prior distribution that biases towards hypotheses with higher values and (ii) a loglikelihood function is set to be the empirical loss evaluated on the historical data, where the choice of loss function supports both model-free and model-based learning. We prove that the proposed algorithm is sample efficient by establishing a sublinear regret upper bound in terms of GEC. In summary, we provide a new and unified understanding of both fully observable and partially observable RL.
translated by 谷歌翻译
鉴于它在提取功能表示方面的力量,对比性的自我监督学习已成功整合到(深)强化学习(RL)的实践中,从而在各种应用程序中提供了有效的政策学习。尽管取得了巨大的经验成功,但对RL的对比学习的理解仍然难以捉摸。为了缩小这样的差距,我们研究了Markov决策过程(MDP)和Markov Games(MGS)的对比度学习如何赋予RL的能力。对于这两种模型,我们建议通过最大程度地减少对比度损失来提取低级别模型的正确特征表示。此外,在在线环境下,我们提出了新颖的上限置信界(UCB)型算法,该算法将这种对比度损失与MDP或MGS的在线RL算法结合在一起。从理论上讲,我们进一步证明了我们的算法恢复了真实表示形式,并同时在学习MDP和MGS中学习最佳策略和NASH平衡方面同时实现了样本效率。我们还提供实证研究,以证明基于UCB的RL的对比度学习方法的功效。据我们所知,我们提供了第一种可证明有效的在线RL算法,该算法结合了代表学习的对比学习。我们的代码可从https://github.com/baichenjia/contrastive-ucb获得。
translated by 谷歌翻译
We study reinforcement learning (RL) with linear function approximation. For episodic time-inhomogeneous linear Markov decision processes (linear MDPs) whose transition dynamic can be parameterized as a linear function of a given feature mapping, we propose the first computationally efficient algorithm that achieves the nearly minimax optimal regret $\tilde O(d\sqrt{H^3K})$, where $d$ is the dimension of the feature mapping, $H$ is the planning horizon, and $K$ is the number of episodes. Our algorithm is based on a weighted linear regression scheme with a carefully designed weight, which depends on a new variance estimator that (1) directly estimates the variance of the \emph{optimal} value function, (2) monotonically decreases with respect to the number of episodes to ensure a better estimation accuracy, and (3) uses a rare-switching policy to update the value function estimator to control the complexity of the estimated value function class. Our work provides a complete answer to optimal RL with linear MDPs, and the developed algorithm and theoretical tools may be of independent interest.
translated by 谷歌翻译
我们在一般的非线性函数近似下研究无奖励增强学习(RL),并在各种标准结构假设下建立样品效率和硬度结果。从积极的一面来看,我们提出了在最小的结构假设下进行样品有效奖励探索的Rfolive(无奖励橄榄)算法,该假设涵盖了先前研究的线性MDPS的设置(Jin等,2020b),线性完整性(线性完整性)( Zanette等人,2020b)和低级MDP,具有未知的表示(Modi等,2021)。我们的分析表明,以前针对后两个设置的易学性或可及性假设在统计上对于无奖励探索而言并不是必需的。在负面方面,我们为在线性完整性假设下的无奖励和奖励意识探索提供统计硬度结果时,当基础特征未知时,显示了低级别和线性完整性设置之间的指数分离。
translated by 谷歌翻译
强化学习算法的实用性由于相对于问题大小的规模差而受到限制,因为学习$ \ epsilon $ -optimal策略的样本复杂性为$ \ tilde {\ omega} \ left(| s | s || a || a || a || a | h^3 / \ eps^2 \ right)$在MDP的最坏情况下,带有状态空间$ S $,ACTION SPACE $ A $和HORIZON $ H $。我们考虑一类显示出低级结构的MDP,其中潜在特征未知。我们认为,价值迭代和低级别矩阵估计的自然组合导致估计误差在地平线上呈指数增长。然后,我们提供了一种新算法以及统计保证,即有效利用了对生成模型的访问,实现了$ \ tilde {o} \ left的样本复杂度(d^5(d^5(| s |+| a |)\),我们有效利用低级结构。对于等级$ d $设置的Mathrm {Poly}(h)/\ EPS^2 \ right)$,相对于$ | s |,| a | $和$ \ eps $的缩放,这是最小值的最佳。与线性和低级别MDP的文献相反,我们不需要已知的功能映射,我们的算法在计算上很简单,并且我们的结果长期存在。我们的结果提供了有关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 谷歌翻译
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 谷歌翻译
在阻碍强化学习(RL)到现实世界中的问题的原因之一,两个因素至关重要:与培训相比,数据有限和测试环境的不匹配。在本文中,我们试图通过分配强大的离线RL的问题同时解决这些问题。特别是,我们学习了一个从源环境中获得的历史数据,并优化了RL代理,并在扰动的环境中表现良好。此外,我们考虑将算法应用于大规模问题的线性函数近似。我们证明我们的算法可以实现$ O(1/\ sqrt {k})$的次级临时性,具体取决于线性函数尺寸$ d $,这似乎是在此设置中使用样品复杂性保证的第一个结果。进行了不同的实验以证明我们的理论发现,显示了我们算法与非持bust算法的优越性。
translated by 谷歌翻译
使用悲观,推理缺乏详尽的勘探数据集时的脱机强化学习最近颇具知名度。尽管它增加了算法的鲁棒性,过于悲观的推理可以在排除利好政策的发现,这是流行的基于红利悲观的问题同样有害。在本文中,我们介绍一般函数近似的Bellman-一致悲观的概念:不是计算逐点下界的值的功能,我们在超过设定的与贝尔曼方程一致的功能的初始状态实现悲观。我们的理论保证只需要贝尔曼封闭性作为探索性的设置标准,其中基于奖金的情况下的悲观情绪未能提供担保。即使在线性函数逼近的特殊情况下更强的表现力假设成立,我们的结果由$ \ mathcal {}Ø(d)在其样品的复杂$在最近的基于奖金的方法改善的时候,动作的空间是有限的。值得注意的是,我们的算法,能够自动适应事后最好的偏差 - 方差折中,而大多数现有的方法中需要调整的额外超参数的先验。
translated by 谷歌翻译
在本文中,我们研究了部分可观察到的动态系统的在线增强学习(RL)。我们专注于预测状态表示(PSRS)模型,该模型是捕获其他知名模型(例如可观察到的马尔可夫决策过程(POMDP))的表达模型。 PSR使用一组未来观察结果的预测表示状态,并完全使用可观察的数量来定义。我们为PSRS开发了一种新型的基于模型的算法,该算法可以在样本复杂性中学习相对于系统的所有相关参数的多项式缩放的近乎最佳策略。我们的算法自然可以与功能近似合作,以扩展到具有较大状态和观察空间的系统。我们表明,给定一个可实现的模型类别,学习近乎最佳策略的样本复杂性仅相对于模型类的统计复杂性,而没有任何明确的多项式依赖性对状态和观察空间的大小依赖。值得注意的是,我们的工作是表明多项式样本复杂性与PSR中全球最佳政策竞争的第一项工作。最后,我们演示了如何直接使用我们的一般定理来得出特殊模型的样本复杂性界限,包括$ m $ $ step弱揭示和$ m $ $ $ - 可解码的表格pomdps,具有低率潜在过渡的POMDP和具有线性pomdps的POMDP排放和潜在过渡。
translated by 谷歌翻译
表示学习通常通过管理维度的诅咒在加强学习中起关键作用。代表性的算法类别利用了随机过渡动力学的光谱分解,以构建在理想化环境中具有强大理论特性的表示。但是,当前的光谱方法的适用性有限,因为它们是用于仅国家的聚合并源自策略依赖性过渡内核的,而无需考虑勘探问题。为了解决这些问题,我们提出了一种替代光谱方法,光谱分解表示(SPEDER),该方法从动力学中提取了国家行动抽象而不诱导虚假依赖数据收集策略,同时还可以平衡探索访问权分析交易 - 在学习过程中关闭。理论分析确定了在线和离线设置中所提出的算法的样本效率。此外,一项实验研究表明,在几个基准测试中,比当前的最新算法表现出色。
translated by 谷歌翻译
Deep latent variable models have achieved significant empirical successes in model-based reinforcement learning (RL) due to their expressiveness in modeling complex transition dynamics. On the other hand, it remains unclear theoretically and empirically how latent variable models may facilitate learning, planning, and exploration to improve the sample efficiency of RL. In this paper, we provide a representation view of the latent variable models for state-action value functions, which allows both tractable variational learning algorithm and effective implementation of the optimism/pessimism principle in the face of uncertainty for exploration. In particular, we propose a computationally efficient planning algorithm with UCB exploration by incorporating kernel embeddings of latent variable models. Theoretically, we establish the sample complexity of the proposed approach in the online and offline settings. Empirically, we demonstrate superior performance over current state-of-the-art algorithms across various benchmarks.
translated by 谷歌翻译
我们研究了具有线性函数近似增强学习中的随机最短路径(SSP)问题,其中过渡内核表示为未知模型的线性混合物。我们将此类别的SSP问题称为线性混合物SSP。我们提出了一种具有Hoeffding-type置信度的新型算法,用于学习线性混合物SSP,可以获得$ \ tilde {\ Mathcal {o}}}}(d B _ {\ star}^{1.5} \ sqrt {k/c_ {k/c_ {k/c_ {k/c_ { \ min}})$遗憾。这里$ k $是情节的数量,$ d $是混合模型中功能映射的维度,$ b _ {\ star} $限制了最佳策略的预期累积成本,$ c _ {\ min}>> 0 $是成本函数的下限。当$ c _ {\ min} = 0 $和$ \ tilde {\ mathcal {o}}}(k^{2/3})$遗憾时,我们的算法也适用于情况。据我们所知,这是第一个具有sublrinear遗憾保证线性混合物SSP的算法。此外,我们设计了精致的伯恩斯坦型信心集并提出了改进的算法,该算法可实现$ \ tilde {\ Mathcal {o}}}(d b _ {\ star} \ sqrt {k/c/c/c {k/c _ {\ min}}) $遗憾。为了补充遗憾的上限,我们还证明了$ \ omega(db _ {\ star} \ sqrt {k})$的下限。因此,我们的改进算法将下限匹配到$ 1/\ sqrt {c _ {\ min}} $ factor和poly-logarithmic因素,从而实现了近乎最佳的遗憾保证。
translated by 谷歌翻译