在本文中，我们研究了部分可观察到的动态系统的在线增强学习（RL）。我们专注于预测状态表示（PSRS）模型，该模型是捕获其他知名模型（例如可观察到的马尔可夫决策过程（POMDP））的表达模型。 PSR使用一组未来观察结果的预测表示状态，并完全使用可观察的数量来定义。我们为PSRS开发了一种新型的基于模型的算法，该算法可以在样本复杂性中学习相对于系统的所有相关参数的多项式缩放的近乎最佳策略。我们的算法自然可以与功能近似合作，以扩展到具有较大状态和观察空间的系统。我们表明，给定一个可实现的模型类别，学习近乎最佳策略的样本复杂性仅相对于模型类的统计复杂性，而没有任何明确的多项式依赖性对状态和观察空间的大小依赖。值得注意的是，我们的工作是表明多项式样本复杂性与PSR中全球最佳政策竞争的第一项工作。最后，我们演示了如何直接使用我们的一般定理来得出特殊模型的样本复杂性界限，包括$ m $ $ step弱揭示和$ m $ $ $ - 可解码的表格pomdps，具有低率潜在过渡的POMDP和具有线性pomdps的POMDP排放和潜在过渡。

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

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

强化学习算法的实用性由于相对于问题大小的规模差而受到限制，因为学习$ \ 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）的现实应用中无处不在。从理论上讲，在最坏情况下，由于指数样本的复杂性下限，在最坏情况下学习了近距离观察性的近乎最佳政策。最近的工作已经确定了几个可通过多项式样本学习的可学性亚类，例如部分可观察到的马尔可夫决策过程（POMDPS）具有某些可揭示或可分解性条件。但是，这一研究仍处于起步阶段，（1）缺乏统一的结构条件，从而缺乏样品效率学习； （2）现有的已知拖拉子类的样品复杂性远非锋利； （3）与完全可观察的RL相比，可用的样品效率算法更少。本文在预测状态表示（PSRS）的一般环境中，上面的所有三个方面都在部分可观察到的RL方向前进。首先，我们提出了一种称为\ emph {b稳定性}的自然和统一的结构条件。 B稳定的PSR包括绝大多数已知的可牵引子类，例如弱揭示的POMDP，低级别的未来pomdps，可解码的POMDP和常规PSR。接下来，我们证明可以在相关问题参数中使用多项式样本学习任何B稳定PSR。当在上述子类中实例化时，我们的样本复杂性比当前最好的复杂性大大改善。最后，我们的结果是通过三种算法同时实现的：乐观的最大似然估计，估计到决策和基于模型的乐观后验采样。后两种算法是用于POMDPS/PSR的样品有效学习的新算法。

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.

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

我们研究了通过功能近似的强化学习，以部分可观察到的马尔可夫决策过程（POMDP），其中状态空间和观察空间很大甚至连续。特别是，我们考虑了POMDP的Hilbert空间嵌入，其中潜在状态的特征和观察的特征允许观测发射过程的有条件的希尔伯特空间嵌入，而潜在状态过渡是确定性的。在函数近似设置下，最佳潜在状态行动$ q $函数在状态功能中是线性的，而最佳$ q $ - 功能具有差距，我们提供了\ emph {计算和统计上有效} algorithm查找\ emph {确切的最佳}策略。我们在观察空间上的算法和特征的固有维度上，在多项式上显示了算法的计算和统计复杂性。此外，我们显示了确定性的潜在过渡和差距假设对于避免统计复杂性指数在地平线或维度中是必要的。由于我们的保证对状态和观察空间的大小没有明确的依赖性，因此我们的算法可证明对大规模POMDPS。

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

我们研究了具有无限观察和状态空间的部分观察到的马尔可夫决策过程（POMDP）的强化学习，理论上仍然不太研究。为此，我们首次尝试弥合具有线性结构的一类POMDP的部分可观察性和功能近似。详细说明，我们建议在$ O（1/\ Epsilon^2）$情节中获得$ \ epsilon $ - 最佳策略的增强学习算法（通过对抗积分方程或操作装置的乐观探索）。特别是，样品复杂性在线性结构的固有维度上缩放，并且独立于观测和状态空间的大小。 Op-Tenet的样品效率由一系列成分启用：（i）具有有限内存的钟形操作员，该操作员以递归方式表示值函数，（ii）通过对抗性积分对此类操作员的识别和估计方程式具有针对线性结构量身定制的平滑歧视器，以及（iii）通过乐观探索观察和状态空间，该探索基于量化对抗性积分方程的不确定性。

这项工作研究了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设置，我们开发了一种利用悲观主义在部分覆盖条件下学习的算法：我们的算法能够与脱机分布所涵盖的策略进行竞争。

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

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

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

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

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）的样本复杂性。值得注意的是，对于具有Horizo​​ n长度$ H $的RL环境，之前的工作表明，使用$ \ mathrm {polylog}（h）有可能学习$ o（1）$ - 最佳策略的可能大致正确（pac）算法$当州和行动的数量固定时的环境交互剧集。它尚不清楚$ \ mathrm {polylog}（h）$依赖性是必要的。在这项工作中，我们通过开发一种算法来解决这个问题，该算法在仅使用ONTO（1）美元的环境交互的同时实现相同的PAC保证，完全解决RL中样本复杂性的地平线依赖性。我们通过（i）在贴现和有限地平线马尔可夫决策过程（MDP）和（ii）在MDP中的新型扰动分析中建立价值函数之间的联系。我们相信我们的新技术具有独立兴趣，可在RL中应用相关问题。

无奖励强化学习（RL）考虑了代理在探索过程中无法访问奖励功能的设置，但必须提出仅在探索后才揭示的任意奖励功能的近乎最佳的政策。在表格环境中，众所周知，这是一个比奖励意识（PAC）RL（代理在探索过程中访问奖励功能）更困难的问题$ | \ Mathcal {s} | $，状态空间的大小。我们表明，在线性MDP的设置中，这种分离不存在。我们首先在$ d $二维线性MDP中开发了一种计算高效算法，其样品复杂度比例为$ \ widetilde {\ Mathcal {o}}（d^2 H^5/\ epsilon^2）$ 。然后，我们显示出$ \ omega（d^2 h^2/\ epsilon^2）$的匹配尺寸依赖性的下限，该限制为奖励感知的RL设置。据我们所知，我们的方法是第一个在线性MDP中实现最佳$ d $依赖性的计算有效算法，即使在单次奖励PAC设置中也是如此。我们的算法取决于一种新的程序，该过程有效地穿越了线性MDP，在任何给定的``特征方向''中收集样品，并在最大状态访问概率（线性MDP等效）中享受最佳缩放样品复杂性。我们表明，该探索过程也可以应用于解决线性MDP中````良好条件''''协变量的问题。

尽管在理解增强学习的最小样本复杂性（RL）（在“最坏情况”的实例上学习的复杂性）方面已经取得了很多进展，但这种复杂性的衡量标准通常不会捕捉到真正的学习困难。在实践中，在“简单”的情况下，我们可能希望获得比最糟糕的实例可以实现的要好得多。在这项工作中，我们试图理解在具有线性函数近似的RL设置中学习近乎最佳策略（PAC RL）的“实例依赖性”复杂性。我们提出了一种算法，\ textsc {pedel}，该算法实现了依赖于实例的复杂性的量度，这是RL中的第一个具有功能近似设置，从而捕获了每个特定问题实例的学习难度。通过一个明确的示例，我们表明\ textsc {pedel}可以在低重晶，最小值 - 最佳算法上获得可证明的收益，并且这种算法无法达到实例 - 最佳速率。我们的方法取决于基于设计的新型实验程序，该程序将勘探预算重点放在与学习近乎最佳政策最相关的“方向”上，并且可能具有独立的兴趣。