我们考虑了离线强化学习问题，其中目的是学习从记录数据的决策策略。离线RL - 特别是当耦合时函数近似时允许在大或连续状态空间中允许泛化 - 在实践中变得越来越相关，因为它避免了昂贵且耗时的在线数据收集，并且非常适合安全 - 关键域名。对于离线值函数近似方法的现有样本复杂性保证通常需要（1）分配假设（即，良好的覆盖率）和（2）代表性假设（即，表示一些或所有$ q $ -value函数的能力）比什么是更强大的受监督学习所必需的。然而，尽管研究了几十年的研究，但仍然无法充分理解这些条件和离线RL的基本限制。这使得陈和江（2019）猜想勇敢地（覆盖范围最大的覆盖率）和可实现性（最弱的代表条件）不足以足以用于样品有效的离线RL。通过证明通常，即使满足勇敢性和可实现性，也要解决这一猜想，即使满足既勇敢性和可实现性，也需要在状态空间的大小中需要采样复杂性多项式以学习非琐碎的政策。我们的研究结果表明，采样高效的离线强化学习需要超越监督学习的限制性覆盖条件或代表条件，并突出显示出称为过度覆盖的现象，该现象用作离线值函数近似方法的基本障碍。通过线性函数近似的加强学习结果的结果是，即使在恒定尺寸，在线和离线RL之间的分离也可以是任意大的。

强化学习算法的实用性由于相对于问题大小的规模差而受到限制，因为学习$ \ 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对过渡内核与最佳动作值函数所需的最小低级结构假设的见解。

大部分强化学习理论都建立在计算上难以实施的甲板上。专门用于在部分可观察到的马尔可夫决策过程（POMDP）中学习近乎最佳的政策，现有算法要么需要对模型动态（例如确定性过渡）做出强有力的假设，要么假设访问甲骨文作为解决艰难的计划或估算问题的访问子例程。在这项工作中，我们在合理的假设下开发了第一个用于POMDP的无Oracle学习算法。具体而言，我们给出了一种用于在“可观察” pomdps中学习的准化性时间端到端算法，其中可观察性是一个假设，即对国家而言，分离良好的分布诱导了分离良好的分布分布而不是观察。我们的技术规定了在不确定性下使用乐观原则来促进探索的更传统的方法，而是在构建策略涵盖的情况下提供了一种新颖的barycentric跨度应用。

在现实世界的强化学习应用中，学习者的观察空间无处不在，有关手头任务的相关信息和无关紧要。从高维观察中学习一直是监督学习和统计数据（例如，通过稀疏性）进行广泛研究的主题，但是即使在有限的状态/行动（表格）领域，也不能很好地理解强化学习中的类似问题。我们引入了一个新的问题设置，用于增强学习，即马尔可夫决策过程（EXOMDP），其中状态空间将（未知）分解成一个小的（或内源性）组件，并且很大的无关（或外源）组件;外源成分独立于学习者的行为，但以任意的，时间相关的方式演变。我们提供了一种新的算法Exorl，该算法学习了一种近乎最佳的政策，其样品复杂性在内源性组件的大小中多项式，几乎独立于外源成分的大小，从而提供了一个双重指数的改进算法。我们的结果首次突出了在存在外源信息的情况下首次可以进行样品高效的增强学习，并为未来的调查提供了简单，用户友好的基准。

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.

本文涉及增强学习的样本效率，假设进入生成模型（或模拟器）。我们首先考虑$ \ gamma $ -discounted infinite-horizo​​ n markov决策过程（mdps）与状态空间$ \ mathcal {s} $和动作空间$ \ mathcal {a} $。尽管有许多先前的作品解决这个问题，但尚未确定样本复杂性和统计准确性之间的权衡的完整图像。特别地，所有事先结果都遭受严重的样本大小屏障，因为只有在样本量超过$ \ FRAC {| \ Mathcal {S} || \ Mathcal {A} |} {（1- \ gamma）^ 2} $。目前的论文通过认证了两种算法的最小值 - 基于模型的算法和基于保守模型的算法的最小值，克服了该障碍 - 一旦样本大小超过$ \ FRAC {| \ Mathcal {s } || mathcal {a} |} {1- \ gamma} $（modulo一些日志系数）。超越无限地平线MDP，我们进一步研究了时代的有限情况MDP，并证明了一种基于普通模型的规划算法足以实现任何目标精度水平的最佳样本复杂性。据我们所知，这项工作提供了第一个最低限度的最佳保证，可容纳全部样本尺寸（超出哪个发现有意义的政策是理论上不可行的信息）。

本文介绍了一项有关离线增强学习中依赖间隙依赖样品复杂性的系统研究。先前的工作显示了何时最佳策略和行为策略之间的密度比上限（最佳策略覆盖范围假设），则代理可以实现$ o \ left（\ frac {1} {\ epsilon^2} \ right）$ rate，这也是最小值的最佳。我们在最佳策略覆盖范围假设下显示，当在最佳$ q $ unction中存在积极的子临时差距时，可以将费率提高到$ o \ left（\ frac {1} {\ epsilon} \ right）$。。此外，我们显示了行为策略的访问概率何时在最佳策略的访问概率为正（统一的最佳策略覆盖范围假设）的状态下，均匀下降，识别最佳政策的样本复杂性独立于$ \ frac {1} {\ epsilon} $。最后，我们呈现几乎匹配的下限，以补充我们的间隙依赖性上限。

In this paper we develop a theoretical analysis of the performance of sampling-based fitted value iteration (FVI) to solve infinite state-space, discounted-reward Markovian decision processes (MDPs) under the assumption that a generative model of the environment is available. Our main results come in the form of finite-time bounds on the performance of two versions of sampling-based FVI. The convergence rate results obtained allow us to show that both versions of FVI are well behaving in the sense that by using a sufficiently large number of samples for a large class of MDPs, arbitrary good performance can be achieved with high probability. An important feature of our proof technique is that it permits the study of weighted L p -norm performance bounds. As a result, our technique applies to a large class of function-approximation methods (e.g., neural networks, adaptive regression trees, kernel machines, locally weighted learning), and our bounds scale well with the effective horizon of the MDP. The bounds show a dependence on the stochastic stability properties of the MDP: they scale with the discounted-average concentrability of the future-state distributions. They also depend on a new measure of the approximation power of the function space, the inherent Bellman residual, which reflects how well the function space is "aligned" with the dynamics and rewards of the MDP. The conditions of the main result, as well as the concepts introduced in the analysis, are extensively discussed and compared to previous theoretical results. Numerical experiments are used to substantiate the theoretical findings.

Value-function approximation methods that operate in batch mode have foundational importance to reinforcement learning (RL). Finite sample guarantees for these methods often crucially rely on two types of assumptions: (1) mild distribution shift, and (2) representation conditions that are stronger than realizability. However, the necessity ("why do we need them?") and the naturalness ("when do they hold?") of such assumptions have largely eluded the literature. In this paper, we revisit these assumptions and provide theoretical results towards answering the above questions, and make steps towards a deeper understanding of value-function approximation.

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.

我们介绍了一种普遍的策略，可实现有效的多目标勘探。它依赖于adagoal，一种基于简单约束优化问题的新的目标选择方案，其自适应地针对目标状态，这既不是太困难也不是根据代理目前的知识达到的。我们展示了Adagoal如何用于解决学习$ \ epsilon $ -optimal的目标条件的政策，以便在$ L $ S_0 $ S_0 $奖励中获得的每一个目标状态，以便在$ S_0 $中获取。免费马尔可夫决策过程。在标准的表格外壳中，我们的算法需要$ \ tilde {o}（l ^ 3 s a \ epsilon ^ { - 2}）$探索步骤，这几乎很少最佳。我们还容易在线性混合Markov决策过程中实例化Adagoal，其产生具有线性函数近似的第一目标导向的PAC保证。除了强大的理论保证之外，迈克纳队以现有方法的高级别算法结构为锚定，为目标条件的深度加固学习。

我们建议和分析一个强化学习原理，该原理仅在测试功能的用户定义空间沿使用它们的有效性来近似钟声方程。我们专注于使用功能近似的无模型离线RL应用程序，我们利用这一原理来得出置信区间以进行非政策评估，并在规定的策略类别中优化了对策略的优化。我们证明了关于我们的政策优化程序的甲骨文不平等，就任意比较策略的价值和不确定性之间的权衡而言。测试功能空间的不同选择使我们能够解决共同框架中的不同问题。我们表征了使用我们的程序从政策转移到政策数据的效率的丧失，并建立了与过去工作中研究的浓缩性系数的连接。我们深入研究了具有线性函数近似的方法的实施，即使贝尔曼关闭不结束，也可以通过多项式时间实现提供理论保证。

本文介绍了一种简单的有效学习算法，用于一般顺序决策。该算法将探索的乐观与模型估计的最大似然估计相结合，因此被命名为OMLE。我们证明，Omle了解了多项式数量的样本中一系列非常丰富的顺序决策问题的近乎最佳策略。这个丰富的类别不仅包括大多数已知的基于模型的基于模型的强化学习（RL）问题（例如表格MDP，计算的MDP，低证人等级问题，表格弱弱/可观察到的POMDP和多步可解码的POMDP），但是同样，许多新的具有挑战性的RL问题，尤其是在可观察到的部分环境中，这些问题以前尚不清楚。值得注意的是，本文解决的新问题包括（1）具有连续观察和功能近似的可观察到的POMDP，在其中我们实现了完全独立于观察空间的第一个样品复杂性； （2）条件良好的低级顺序决策问题（也称为预测状态表示（PSRS）），其中包括并概括了所有已知的可牵引的POMDP示例，这些示例在更固有的表示下； （3）在帆条件下进行一般顺序决策问题，这统一了我们在完全可观察和部分可观察的设置中对基于模型的RL的现有理解。帆条件是由本文确定的，可以将其视为贝尔曼/证人等级的自然概括，以解决部分可观察性。

在线学习和决策中的一个核心问题 - 从土匪到强化学习 - 是要了解哪种建模假设会导致样本有效的学习保证。我们考虑了一个普遍的对抗性决策框架，该框架涵盖了（结构化的）匪徒问题，这些问题与对抗性动力学有关。我们的主要结果是通过新的上限和下限显示决策估计系数，这是Foster等人引入的复杂度度量。在与我们环境的随机对应物中，对于对抗性决策而言是必要和足够的遗憾。但是，与随机设置相比，必须将决策估计系数应用于所考虑的模型类（或假设）的凸壳。这就确定了容纳对抗奖励或动态的价格受凸层化模型类的行为的约束，并恢复了许多现有结果 - 既积极又负面。在获得这些保证的途径中，我们提供了新的结构结果，将决策估计系数与其他众所周知的复杂性度量的变体联系起来，包括Russo和Van Roy的信息比以及Lattimore和Gy的探索目标\“ {o} rgy。

我们考虑在离线增强学习中有一个具有挑战性的理论问题（RL）：仅在功能近似器的可靠性型假设下，通过缺乏足够覆盖的数据集获得样本效率保证。尽管现有的理论已经在可实现性和非探索数据下分别解决了学习，但没有工作能够同时解决这两者（除了我们对详细比较的并发工作除外）。在额外的差距假设下，我们根据边缘化重要性采样（MIS）形成的版本空间（MIS）为简单的悲观算法提供保证，并且保证只需要数据来涵盖最佳策略和功能类，以实现最佳价值和最佳价值和密度比函数。尽管在RL理论的其他领域中使用了类似的差距假设，但我们的工作是第一个识别离线RL中差距假设的实用性和新型机制，其功能近似较弱。

我们研究了情节块MDP中模型估计和无奖励学习的问题。在这些MDP中，决策者可以访问少数潜在状态产生的丰富观察或上下文。我们首先对基于固定行为策略生成的数据估算潜在状态解码功能（从观测到潜在状态的映射）感兴趣。我们在估计此功能的错误率上得出了信息理论的下限，并提出了接近此基本限制的算法。反过来，我们的算法还提供了MDP的所有组件的估计值。然后，我们研究在无奖励框架中学习近乎最佳政策的问题。根据我们有效的模型估计算法，我们表明我们可以以最佳的速度推断出策略（随着收集样品的数量增长大）的最佳策略。有趣的是，我们的分析提供了必要和充分的条件，在这些条件下，利用块结构可以改善样本复杂性，以识别近乎最佳的策略。当满足这些条件时，Minimax无奖励设置中的样本复杂性将通过乘法因子$ n $提高，其中$ n $是可能的上下文数量。

使用悲观，推理缺乏详尽的勘探数据集时的脱机强化学习最近颇具知名度。尽管它增加了算法的鲁棒性，过于悲观的推理可以在排除利好政策的发现，这是流行的基于红利悲观的问题同样有害。在本文中，我们介绍一般函数近似的Bellman-一致悲观的概念：不是计算逐点下界的值的功能，我们在超过设定的与贝尔曼方程一致的功能的初始状态实现悲观。我们的理论保证只需要贝尔曼封闭性作为探索性的设置标准，其中基于奖金的情况下的悲观情绪未能提供担保。即使在线性函数逼近的特殊情况下更强的表现力假设成立，我们的结果由$ \ mathcal {}Ø（d）在其样品的复杂$在最近的基于奖金的方法改善的时候，动作的空间是有限的。值得注意的是，我们的算法，能够自动适应事后最好的偏差 - 方差折中，而大多数现有的方法中需要调整的额外超参数的先验。

离线增强学习（RL）的样本效率保证通常依赖于对功能类别（例如Bellman-Completeness）和数据覆盖范围（例如，全政策浓缩性）的强有力的假设。尽管最近在放松这些假设方面做出了努力，但现有作品只能放松这两个因素之一，从而使另一个因素的强烈假设完好无损。作为一个重要的开放问题，我们是否可以实现对这两个因素的假设较弱的样本效率离线RL？在本文中，我们以积极的态度回答了这个问题。我们基于MDP的原始偶对偶进行分析了一种简单的算法，其中双重变量（打折占用）是使用密度比函数对离线数据进行建模的。通过适当的正则化，我们表明该算法仅在可变性和单极浓缩性下具有多项式样品的复杂性。我们还基于不同的假设提供了替代分析，以阐明离线RL原始二算法的性质。

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.

本文涉及离线增强学习（RL）中模型鲁棒性和样本效率的核心问题，该问题旨在学习从没有主动探索的情况下从历史数据中执行决策。由于环境的不确定性和变异性，至关重要的是，学习强大的策略（尽可能少的样本），即使部署的环境偏离用于收集历史记录数据集的名义环境时，该策略也能很好地执行。我们考虑了离线RL的分布稳健公式，重点是标签非平稳的有限摩托稳健的马尔可夫决策过程，其不确定性设置为Kullback-Leibler Divergence。为了与样本稀缺作用，提出了一种基于模型的算法，该算法将分布强劲的价值迭代与面对不确定性时的悲观原理结合在一起，通过对稳健的价值估计值进行惩罚，以精心设计的数据驱动的惩罚项进行惩罚。在对历史数据集的轻度和量身定制的假设下，该数据集测量分布变化而不需要完全覆盖州行动空间，我们建立了所提出算法的有限样本复杂性，进一步表明，鉴于几乎无法改善的情况，匹配信息理论下限至地平线长度的多项式因素。据我们所知，这提供了第一个在模型不确定性和部分覆盖范围内学习的近乎最佳的稳健离线RL算法。