本文提供了一项理论研究，该研究对在线环境下的$ \ 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。

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二次地量表。我们通过具体的例子进一步证明，由于相应的动态和奖励结构，在近视探索成功的几项任务中，近视探索差距确实是有利的。

离线增强学习（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内核空间和神经切线内核的范围。

我们研究了受限的强化学习问题，其中代理的目的是最大程度地提高预期的累积奖励，从而受到对实用程序函数的预期总价值的约束。与现有的基于模型的方法或无模型方法伴随着“模拟器”，我们旨在开发第一个无模型的无模拟算法，即使在大规模系统中，也能够实现sublinear遗憾和透明度的约束侵犯。为此，我们考虑具有线性函数近似的情节约束决策过程，其中过渡动力学和奖励函数可以表示为某些已知功能映射的线性函数。我们表明$ \ tilde {\ mathcal {o}}（\ sqrt {d^3h^3t}）$遗憾和$ \ tilde {\ tillcal {\ mathcal {o}}（\ sqrt {d^3h^3ht}）$约束$约束$约束可以实现违规范围，其中$ d $是功能映射的尺寸，$ h $是情节的长度，而$ t $是总数的总数。我们的界限是在没有明确估计未知过渡模型或需要模拟器的情况下达到的，并且仅通过特征映射的维度依赖于状态空间。因此，即使国家的数量进入无穷大，我们的界限也会存在。我们的主要结果是通过标准LSVI-UCB算法的新型适应来实现的。特别是，我们首先将原始二次优化引入LSVI-UCB算法中，以在遗憾和违反约束之间取得平衡。更重要的是，我们使用软马克斯政策取代了LSVI-UCB中的状态行动功能的标准贪婪选择。事实证明，这对于通过其近似平滑度的权衡来确定受约束案例的统一浓度是关键。我们还表明，一个人可以达到均匀的约束违规行为，同时仍然保持相同的订单相对于$ t $。

汤普森采样是上下文匪徒的最有效方法之一，已被推广到某些MDP设置后的后验采样。但是，现有的后验学习方法是基于模型或缺乏线性MDP以外的最坏情况的理论保证而受到限制的。本文提出了一种新的无模型后取样公式，该公式适用于具有理论保证的更通用的情节增强学习问题。我们介绍了新颖的证明技术，以表明在适当的条件下，我们的后抽样方法的最遗憾与基于优化的方法的最著名结果相匹配。在具有尺寸的线性MDP设置中，与现有基于后采样的探索算法的二次依赖性相比，我们算法的遗憾与维度线性缩放。

强化学习（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总体上，轨迹奖励的效率非常有效。

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.

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

我们研究马尔可夫决策过程（MDP）框架中的离线数据驱动的顺序决策问题。为了提高学习政策的概括性和适应性，我们建议通过一套关于在政策诱导的固定分配所在的分发的一套平均奖励来评估每项政策。给定由某些行为策略生成的多个轨迹的预收集数据集，我们的目标是在预先指定的策略类中学习一个强大的策略，可以最大化此集的最小值。利用半参数统计的理论，我们开发了一种统计上有效的策略学习方法，用于估算DE NED强大的最佳政策。在数据集中的总决策点方面建立了达到对数因子的速率最佳遗憾。

我们在无限地平线马尔可夫决策过程中考虑批量（离线）策略学习问题。通过移动健康应用程序的推动，我们专注于学习最大化长期平均奖励的政策。我们为平均奖励提出了一款双重强大估算器，并表明它实现了半导体效率。此外，我们开发了一种优化算法来计算参数化随机策略类中的最佳策略。估计政策的履行是通过政策阶级的最佳平均奖励与估计政策的平均奖励之间的差异来衡量，我们建立了有限样本的遗憾保证。通过模拟研究和促进体育活动的移动健康研究的分析来说明该方法的性能。

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

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.

我们研究了具有线性函数近似增强学习中的随机最短路径（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因素，从而实现了近乎最佳的遗憾保证。

本文以非线性功能近似研究基于模型的匪徒和增强学​​习（RL）。我们建议研究与近似局部最大值的收敛性，因为我们表明，即使对于具有确定性奖励的一层神经网络匪徒，全球收敛在统计上也很棘手。对于非线性匪徒和RL，本文介绍了一种基于模型的算法，即具有在线模型学习者（小提琴）的虚拟攀登，该算法可证明其收敛到局部最大值，其样品复杂性仅取决于模型类的顺序Rademacher复杂性。我们的结果意味着在几种具体设置（例如有限或稀疏模型类别的线性匪徒）和两层神经净匪内的新型全球或本地遗憾界限。一个关键的算法洞察力是，即使对于两层神经净模型类别，乐观也可能导致过度探索。另一方面，为了收敛到本地最大值，如果模型还可以合理地预测真实返回的梯度和Hessian的大小，则足以最大化虚拟返回。

在表格设置下，我们研究了折扣马尔可夫决策过程（MDP）的强化学习问题。我们提出了一种名为UCBVI - $ \ Gamma $的基于模型的算法，该算法基于\ emph {面对不确定原理}和伯尔斯坦型奖金的乐观。我们展示了UCBVI - $ \ Gamma $实现了一个$ \ tilde {o} \ big（{\ sqrt {sat}} / {（1- \ gamma）^ {1.5}} \ big）$后悔，在哪里$ s $是州的数量，$ a $是行动的数量，$ \ gamma $是折扣因子，$ t $是步数。此外，我们构建了一类硬MDP并表明对于任何算法，预期的遗憾是至少$ \ tilde {\ omega} \ big（{\ sqrt {sat}} / {（1- \ gamma）^ {1.5}} \大）$。我们的上限与对数因子的最低限度相匹配，这表明UCBVI - $ \ Gamma $几乎最小的贴现MDP。

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

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.

Model-free reinforcement learning (RL) algorithms, such as Q-learning, directly parameterize and update value functions or policies without explicitly modeling the environment. They are typically simpler, more flexible to use, and thus more prevalent in modern deep RL than model-based approaches. However, empirical work has suggested that model-free algorithms may require more samples to learn [7,22]. The theoretical question of "whether model-free algorithms can be made sample efficient" is one of the most fundamental questions in RL, and remains unsolved even in the basic scenario with finitely many states and actions.We prove that, in an episodic MDP setting, Q-learning with UCB exploration achieves regret Õ( √ H 3 SAT ), where S and A are the numbers of states and actions, H is the number of steps per episode, and T is the total number of steps. This sample efficiency matches the optimal regret that can be achieved by any model-based approach, up to a single √ H factor. To the best of our knowledge, this is the first analysis in the model-free setting that establishes √ T regret without requiring access to a "simulator." * The first two authors contributed equally.

我们考虑在离线域中的强化学习（RL）方法，没有其他在线数据收集，例如移动健康应用程序。计算机科学文献中的大多数现有策略优化算法都是在易于收集或模拟的在线设置中开发的。通过预采用的离线数据集，它们对移动健康应用程序的概括尚不清楚。本文的目的是开发一个新颖的优势学习框架，以便有效地使用预采用的数据进行策略优化。所提出的方法采用由任何现有的最新RL算法计算的最佳Q-估计器作为输入，并输出一项新策略，其价值比基于初始Q-得出的策略更快地收敛速度。估计器。进行广泛的数值实验以支持我们的理论发现。我们提出的方法的Python实现可在https://github.com/leyuanheart/seal上获得。