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.

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.

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

我们在一般的非线性函数近似下研究无奖励增强学习（RL），并在各种标准结构假设下建立样品效率和硬度结果。从积极的一面来看，我们提出了在最小的结构假设下进行样品有效奖励探索的Rfolive（无奖励橄榄）算法，该假设涵盖了先前研究的线性MDPS的设置（Jin等，2020b），线性完整性（线性完整性）（ Zanette等人，2020b）和低级MDP，具有未知的表示（Modi等，2021）。我们的分析表明，以前针对后两个设置的易学性或可及性假设在统计上对于无奖励探索而言并不是必需的。在负面方面，我们为在线性完整性假设下的无奖励和奖励意识探索提供统计硬度结果时，当基础特征未知时，显示了低级别和线性完整性设置之间的指数分离。

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

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

低级MDP已成为研究强化学习中的表示和探索的重要模型。有了已知的代表，存在几种无模型的探索策略。相反，未知表示设置的所有算法都是基于模型的，因此需要对完整动力学进行建模。在这项工作中，我们介绍了低级MDP的第一个无模型表示学习算法。关键的算法贡献是一个新的Minimax表示学习目标，我们为其提供具有不同权衡的变体，其统计和计算属性不同。我们将这一表示的学习步骤与探索策略交织在一起，以无奖励的方式覆盖状态空间。所得算法可证明样品有效，并且可以适应一般函数近似以扩展到复杂的环境。

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

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

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

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.

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

强化学习理论集中在两个基本问题上：实现低遗憾，并确定$ \ epsilon $ - 最佳政策。虽然简单的减少允许人们应用低温算法来获得$ \ epsilon $ - 最佳政策并达到最坏的最佳速率，但尚不清楚低regret算法是否可以获得实例 - 最佳率的策略识别率。我们表明这是不可能的 - 在遗憾和确定$ \ epsilon $ - 最佳政策之间以最佳的利率确定了基本的权衡。由于我们的负面发现，我们提出了针对PAC表格增强学习实例依赖性样本复杂性的新量度，该方法明确说明了基础MDP中可达到的国家访问分布。然后，我们提出和分析一种基于计划的新型算法，该算法达到了这种样本的复杂性 - 产生的复杂性会随着次要差距和状态的“可达到性”而缩放。我们显示我们的算法几乎是最小的最佳选择，并且在一些示例中，我们实例依赖性样品复杂性比最差案例界限可显着改善。

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.

我们研究使用功能近似的部分可观察到的动力学系统的增强学习。我们提出了一个新的\ textit {部分可观察到的双线性actor-Critic-Critic框架}，它足以包括可观察到的图表部分可观察到的Markov决策过程（POMDPS），可观察到的线性Quadratic-Quadratic-Gaussian（LQG）（LQG），预测状态表示（POMDPS）（ PSRS），以及新引入的模型Hilbert空间嵌入POMDPS和可观察到的POMDP，具有潜在的低级过渡。在此框架下，我们提出了一种能够执行不可知论政策学习的参与者批评算法。给定一个由基于内存的策略组成的策略类别（查看最近观察的固定长度窗口），以及一个值得将内存和未来观察作为输入的功能组成的值函数类别，我们的算法学会了与最佳的最佳竞争在给定策略类中基于内存的策略。对于某些示例，例如可观察到的表格pomdps，可观察到的LQG和可观察到的具有潜在低级过渡的可观察到的POMDP，通过隐式利用其特殊特性，我们的算法甚至能够与全球最佳策略竞争，而无需支付对高度依赖的依赖，以竞争全球最佳的策略。它的样本复杂性。

我们在$ \ Gamma $ -diScounted MDP中使用Polyak-Ruppert平均（A.K.A.，平均Q-Leaning）进行同步Q学习。我们为平均迭代$ \ bar {\ boldsymbol {q}}建立渐近常态。此外，我们展示$ \ bar {\ boldsymbol {q}} _ t $实际上是一个常规的渐近线性（RAL）估计值，用于最佳q-value函数$ \ boldsymbol {q} ^ * $与最有效的影响功能。它意味着平均Q学习迭代在所有RAL估算器之间具有最小的渐近方差。此外，我们为$ \ ell _ {\ infty} $错误$ \ mathbb {e} \ | \ | \ bar {\ boldsymbol {q}} _ t- \ boldsymbol {q} ^ *} ^ *} _ {\ idty} $，显示它与实例相关的下限以及最佳最低限度复杂性下限。作为一个副产品，我们发现Bellman噪音具有var-gaussian坐标，具有方差$ \ mathcal {o}（（1- \ gamma）^ {-1}）$而不是现行$ \ mathcal {o}（（1- \ Gamma）^ { - 2}）$根据标准界限奖励假设。子高斯结果有可能提高许多R1算法的样本复杂性。简而言之，我们的理论分析显示平均Q倾斜在统计上有效。

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

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

深度加强学习（RL）由Q函数的神经网络近似，具有巨大的经验成功。虽然RL的理论传统上专注于线性函数近似（或雕刻尺寸）方法，但是关于非线性RL的近似已知Q功能的神经网络近似。这是这项工作的重点，在那里我们研究了与双层神经网络的函数逼近（考虑到Relu和多项式激活功能）。我们的第一个结果是在两层神经网络的完整性下的生成模型设置中的计算上和统计学高效的算法。我们的第二个结果考虑了这个设置，而是通过神经网络函数类的可实现性。这里，假设确定性动态，样本复杂度在代数维度中线性缩放。在所有情况下，我们的结果显着改善了线性（或雕刻尺寸）方法可以获得的。