离线增强学习（RL）利用了先前收集的数据进行策略优化，而无需进行任何进一步的积极探索。尽管最近对这个问题引起了人们的兴趣，但其对神经网络功能近似设置的理论结果仍然有限。在本文中，我们研究了具有深层Relu网络函数近似的离线RL的统计理论。特别是，我们建立了$ \ tilde {\ mathcal {o}} \ left（\ kappa^{1 + d/\ alpha} \ cdot \ epsilon^{ - 2-2-2d/\ alpha} \ right）的样本复杂度$ for Offline RL带有深层relu网络，其中$ \ kappa $是分配变化的度量，$ d $是国家行动空间的尺寸，$ \ alpha $是基础马尔可夫的（可能是分数）平滑度参数决策过程（MDP）和$ \ epsilon $是用户指定的错误。值得注意的是，我们的样本复杂性在两个新颖的考虑因素下，即动态闭合和离线RL的价值回归产生的相关结构。尽管BESOV动态闭合在先前的作品中概括了离线RL的动态条件，但相关结构使离线RL的先前工作与常规/神经网络功能近似不当或效率低下。据我们所知，这是离线RL样品复杂性具有深层神经网络功能近似的第一个理论表征，该效果在普遍的BESOV规律性条件下，超出了传统的繁殖Hilbert内核空间和神经切线内核的范围。

我们研究了用线性函数近似的加固学习中的违规评估（OPE）问题，旨在根据行为策略收集的脱机数据来估计目标策略的价值函数。我们建议纳入价值函数的方差信息以提高ope的样本效率。更具体地说，对于时间不均匀的epiSodic线性马尔可夫决策过程（MDP），我们提出了一种算法VA-OPE，它使用价值函数的估计方差重新重量拟合Q迭代中的Bellman残差。我们表明我们的算法达到了比最着名的结果绑定的更紧密的误差。我们还提供了行为政策与目标政策之间的分布转移的细粒度。广泛的数值实验证实了我们的理论。

我们在使用函数近似的情况下，在使用最小的Minimax方法估算这些功能时，使用功能近似来实现函数近似和$ q $ functions的理论表征。在各种可靠性和完整性假设的组合下，我们表明Minimax方法使我们能够实现重量和质量功能的快速收敛速度，其特征在于关键的不平等\ citep {bartlett2005}。基于此结果，我们分析了OPE的收敛速率。特别是，我们引入了新型的替代完整性条件，在该条件下，OPE是可行的，我们在非尾部环境中以一阶效率提出了第一个有限样本结果，即在领先期限中具有最小的系数。

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.

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

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.

我们研究了离线加强学习（RL）的代表性学习，重点是离线政策评估（OPE）的重要任务。最近的工作表明，与监督的学习相反，Q功能的可实现性不足以学习。样品效率OPE的两个足够条件是Bellman的完整性和覆盖范围。先前的工作通常假设给出满足这些条件的表示形式，结果大多是理论上的。在这项工作中，我们提出了BCRL，该BCRL直接从数据中吸取了近似线性的贝尔曼完整表示，并具有良好的覆盖范围。通过这种学识渊博的表示，我们使用最小平方策略评估（LSPE）执行OPE，并在我们学习的表示中具有线性函数。我们提出了端到端的理论分析，表明我们的两阶段算法享有多项式样本复杂性，该算法在所考虑的丰富类别中提供了一些表示形式，这是线性的贝尔曼完成。从经验上讲，我们广泛评估了我们的DeepMind Control Suite的具有挑战性的基于图像的连续控制任务。我们显示我们的表示能够与针对非政策RL开发的先前表示的学习方法（例如Curl，SPR）相比，可以更好地使用OPE。 BCRL使用最先进的方法拟合Q评估（FQE）实现竞争性OPE误差，并在评估超出初始状态分布的评估时击败FQE。我们的消融表明，我们方法的线性铃铛完整和覆盖范围都至关重要。

随着代表性学习成为一种在实践中降低增强学习（RL）样本复杂性（RL）的强大技术，对其优势的理论理解仍然是有限的。在本文中，我们从理论上表征了在低级马尔可夫决策过程（MDP）模型下表示学习的好处。我们首先研究多任务低级RL（作为上游培训），所有任务都共享一个共同的表示，并提出了一种称为加油的新型多任务奖励算法。加油站同时了解每个任务的过渡内核和近乎最佳的策略，并为下游任务输出良好的代表。我们的结果表明，只要任务总数高于一定的阈值，多任务表示学习比单独学习的样本效率要高。然后，我们研究在线和离线设置中的下游RL，在该设置中，代理商分配了一个新任务，共享与上游任务相同的表示形式。对于在线和离线设置，我们都会开发出样本效率高的算法，并表明它找到了一个近乎最佳的策略，其次要差距在上游中学习的估计误差和一个消失的术语作为数字作为数字的估计误差的范围。下游样品的大量变大。我们在线和离线RL的下游结果进一步捕获了从上游采用学习的表示形式的好处，而不是直接学习低级模型的表示。据我们所知，这是第一个理论研究，它表征了代表性学习在基于探索的无奖励多任务RL中对上游和下游任务的好处。

本文提供了一项理论研究，该研究对在线环境下的$ \ epsilon $ - 梅迪探索中的增强学习（RL）中的深神经功能近似（RL）提供了研究。这种问题设置是由属于该制度的成功深Q-Networks（DQN）框架所激发的。在这项工作中，我们从函数类别和神经网络体系结构（例如，宽度和深度）的角度从“线性”制度之外的函数类别和神经网络体系结构（例如宽度和深度）提供了对理论理解的初步尝试。具体来说，我们将重点放在基于价值的算法上，分别通过BESOV（和Barron）功能空间赋予的深层（和两层）神经网络，以$ \ epsilon $ greedy探索，旨在近似于$ \ alpha $ -Smooth Q功能在$ d $二维功能空间中。我们证明，使用$ t $情节，缩放宽度$ m = \ widetilde {\ mathcal {o}}}（t^{\ frac {d} {2 \ alpha + d}}）$和depth $ l = \ Mathcal {O}（\ log t）for Deep RL的神经网络的$足以在Besov空间中以sublinear的遗憾学习。此外，对于由Barron空间赋予的两层神经网络，缩放宽度$ \ omega（\ sqrt {t}）$就足够了。为了实现这一目标，我们分析中的关键问题是如何估计深神经功能近似下的时间差异误差，因为$ \ epsilon $ - 否则探索不足以确保“乐观”。我们的分析重新制定了$ l^2（\ mathrm {d} \ mu）$ - 在某个平均度量$ \ mu $上的可集成空间，并将其转换为非IID设置下的概括问题。这可能对RL理论具有自身的兴趣，以便更好地理解Deep RL中的$ \ Epsilon $ -Greedy Exploration。

本文涉及增强学习的样本效率，假设进入生成模型（或模拟器）。我们首先考虑$ \ 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，并证明了一种基于普通模型的规划算法足以实现任何目标精度水平的最佳样本复杂性。据我们所知，这项工作提供了第一个最低限度的最佳保证，可容纳全部样本尺寸（超出哪个发现有意义的政策是理论上不可行的信息）。

在阻碍强化学习（RL）到现实世界中的问题的原因之一，两个因素至关重要：与培训相比，数据有限和测试环境的不匹配。在本文中，我们试图通过分配强大的离线RL的问题同时解决这些问题。特别是，我们学习了一个从源环境中获得的历史数据，并优化了RL代理，并在扰动的环境中表现良好。此外，我们考虑将算法应用于大规模问题的线性函数近似。我们证明我们的算法可以实现$ O（1/\ sqrt {k}）$的次级临时性，具体取决于线性函数尺寸$ d $，这似乎是在此设置中使用样品复杂性保证的第一个结果。进行了不同的实验以证明我们的理论发现，显示了我们算法与非持bust算法的优越性。

We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. Focusing on a stochastic query model that provides noisy evaluations of the operator, we analyze a variance-reduced stochastic approximation scheme, and establish non-asymptotic bounds for both the operator defect and the estimation error, measured in an arbitrary semi-norm. In contrast to worst-case guarantees, our bounds are instance-dependent, and achieve the local asymptotic minimax risk non-asymptotically. For linear operators, contractivity can be relaxed to multi-step contractivity, so that the theory can be applied to problems like average reward policy evaluation problem in reinforcement learning. We illustrate the theory via applications to stochastic shortest path problems, two-player zero-sum Markov games, as well as policy evaluation and $Q$-learning for tabular Markov decision processes.

强大的增强学习（RL）的目的是学习一项与模型参数不确定性的强大策略。由于模拟器建模错误，随着时间的推移，现实世界系统动力学的变化以及对抗性干扰，参数不确定性通常发生在许多现实世界中的RL应用中。强大的RL通常被称为最大问题问题，其目的是学习最大化价值与不确定性集合中最坏可能的模型的策略。在这项工作中，我们提出了一种称为鲁棒拟合Q-材料（RFQI）的强大RL算法，该算法仅使用离线数据集来学习最佳稳健策略。使用离线数据的强大RL比其非持续性对应物更具挑战性，因为在强大的Bellman运营商中所有模型的最小化。这在离线数据收集，对模型的优化以及公正的估计中构成了挑战。在这项工作中，我们提出了一种系统的方法来克服这些挑战，从而导致了我们的RFQI算法。我们证明，RFQI在标准假设下学习了一项近乎最佳的强大政策，并证明了其在标准基准问题上的出色表现。

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.

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.

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

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.

Epsilon-Greedy，SoftMax或Gaussian噪声等近视探索政策在某些强化学习任务中无法有效探索，但是在许多其他方面，它们的表现都很好。实际上，实际上，由于简单性，它们通常被选为最佳选择。但是，对于哪些任务执行此类政策成功？我们可以为他们的有利表现提供理论保证吗？尽管这些政策具有显着的实际重要性，但这些关键问题几乎没有得到研究。本文介绍了对此类政策的理论分析，并为通过近视探索提供了对增强学习的首次遗憾和样本复杂性。我们的结果适用于具有有限的Bellman Eluder维度的情节MDP中的基于价值功能的算法。我们提出了一种新的复杂度度量，称为近视探索差距，用Alpha表示，该差距捕获了MDP的结构属性，勘探策略和给定的值函数类别。我们表明，近视探索的样品复杂性与该数量的倒数1 / alpha^2二次地量表。我们通过具体的例子进一步证明，由于相应的动态和奖励结构，在近视探索成功的几项任务中，近视探索差距确实是有利的。