寻找统一的复杂性度量和样本效率学习的算法是增强学习研究的核心主题（RL）。 Foster等人最近提出了决策估计系数（DEC）。 （2021）作为样品有效的NO-REGRET RL的必要和足够的复杂度度量。本文通过DEC框架朝着RL的统一理论取得了进步。首先，我们提出了两项​​新的DEC类型复杂性度量：探索性DEC（EDEC）和无奖励DEC（RFDEC）。我们表明，它们对于样本有效的PAC学习和无奖励学习是必要的，因此扩展了原始DEC，该DEC仅捕获了无需重新学习。接下来，我们为所有三个学习目标设计新的统一样品效率算法。我们的算法实例化估计到决策的变体（E2D）元算法具有强大而通用的模型估计值。即使在无重组的设置中，我们的算法E2D-TA也会在Foster等人的算法上提高。 （2021）需要对DEC的变体进行边界，该变体可能是过于大的，或者设计特定问题的估计值。作为应用程序，我们恢复了现有的，并获得了使用单个算法的各种可拖动RL问题的新样品学习结果。最后，作为一种连接，我们根据后采样或最大似然估计重新分析了两种现有的基于乐观模型的算法，表明它们在与DEC相似的结构条件下具有与E2D-TA相似的遗憾界限。

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

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.

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

我们提出了一个通用框架，以设计基于模型的RL的后验采样方法。我们表明，可以通过减少基于Hellinger距离的条件概率估计的遗憾来分析所提出的算法。我们进一步表明，当我们通过数据可能性测量模型误差时，乐观的后采样可以控制此Hellinger距离。该技术使我们能够设计和分析许多基于模型的RL设置的最先进的样品复杂性保证的统一后采样算法。我们在许多特殊情况下说明了我们的总体结果，证明了我们框架的多功能性。

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

在本文中，我们研究了强大的马尔可夫决策过程（MDPS）的最佳稳健策略和价值功能的非反应性和渐近性能，其中仅从生成模型中求解了最佳的稳健策略和价值功能。尽管在KL不确定性集和$（s，a）$ - 矩形假设的设置中限制了以前专注于可靠MDP的非反应性能的工作，但我们改善了它们的结果，还考虑了其​​他不确定性集，包括$ L_1 $和$ L_1 $和$ \ chi^2 $球。我们的结果表明，当我们假设$（s，a）$ - 矩形在不确定性集上时，示例复杂度大约为$ \ widetilde {o} \ left（\ frac {| \ mathcal {| \ mathcal {s} |^2 | \ mathcal { a} |} {\ varepsilon^2 \ rho^2（1- \ gamma）^4} \ right）$。此外，我们将结果从$（s，a）$ - 矩形假设扩展到$ s $矩形假设。在这种情况下，样本复杂性随选择不确定性集而变化，通常比$（s，a）$矩形假设下的情况大。此外，我们还表明，在$（s，a）$和$ s $ retectangular的假设下，从理论和经验的角度来看，最佳的鲁棒值函数是渐近的正常，典型的速率$ \ sqrt {n} $。

We study model-based reinforcement learning (RL) for episodic Markov decision processes (MDP) whose transition probability is parametrized by an unknown transition core with features of state and action. Despite much recent progress in analyzing algorithms in the linear MDP setting, the understanding of more general transition models is very restrictive. In this paper, we establish a provably efficient RL algorithm for the MDP whose state transition is given by a multinomial logistic model. To balance the exploration-exploitation trade-off, we propose an upper confidence bound-based algorithm. We show that our proposed algorithm achieves $\tilde{\mathcal{O}}(d \sqrt{H^3 T})$ regret bound where $d$ is the dimension of the transition core, $H$ is the horizon, and $T$ is the total number of steps. To the best of our knowledge, this is the first model-based RL algorithm with multinomial logistic function approximation with provable guarantees. We also comprehensively evaluate our proposed algorithm numerically and show that it consistently outperforms the existing methods, hence achieving both provable efficiency and practical superior performance.

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.

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

近年来，动态机制设计引起了计算机科学家和经济学家的极大关注。通过允许代理商在多个回合中与卖方互动，在这种情况下，代理商的奖励功能可能会随着时间而变化并且与国家有关，该框架能够建模丰富的现实世界问题。在这些作品中，通常认为代理商和卖方之间的相互作用遵循马尔可夫决策过程（MDP）。我们专注于此类MDP的奖励和过渡函数的设置，而不是先验地知道，我们正在尝试使用先验收集的数据集恢复最佳机制。在使用函数近似来处理大型状态空间的情况下，只有对功能类表达式的轻度假设，我们能够使用离线增强学习算法设计动态机制。此外，学到的机制大约具有三个关键的逃避：效率，个人理性和真实性。我们的算法基于悲观原则，仅需要对离线数据集的覆盖率进行温和的假设。据我们所知，我们的工作为动态机制设计提供了第一个离线RL算法，而无需假设覆盖范围。

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

部署效率是许多实际应用程序应用（RL）的重要标准。尽管社区的兴趣越来越大，但对于该问题缺乏正式的理论表述。在本文中，我们从“具有约束的优化”的角度提出了一种用于部署有效的RL（DE-RL）的公式：我们有兴趣探索MDP并在最小值{部署复杂性}中获得近乎最佳的策略。 ，而在每个部署中，策略可以采样大量数据。使用有限的摩尼子线性MDP作为具体的结构模型，我们通过建立信息理论下限，并提供实现最佳部署效率的算法来揭示实现部署效率的基本限制。此外，我们对DE-RL的配方是灵活的，可以作为其他实际相关设置的基础；我们将“安全的DE-RL”和“样本有效的DE-RL”作为两个例子，这可能是值得将来的研究。

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

了解现代机器学习设置中的概括一直是统计学习理论的主要挑战之一。在这种情况下，近年来见证了各种泛化范围的发展，表明了不同的复杂性概念，例如数据样本和算法输出之间的相互信息，假设空间的可压缩性以及假设空间的分形维度。尽管这些界限从不同角度照亮了手头的问题，但它们建议的复杂性概念似乎似乎无关，从而限制了它们的高级影响。在这项研究中，我们通过速率理论的镜头证明了新的概括界定，并明确地将相互信息，可压缩性和分形维度的概念联系起来。我们的方法包括（i）通过使用源编码概念来定义可压缩性的广义概念，（ii）表明“压缩错误率”可以与预期和高概率相关。我们表明，在“无损压缩”设置中，我们恢复并改善了现有的基于信息的界限，而“有损压缩”方案使我们能够将概括与速率延伸维度联系起来，这是分形维度的特定概念。我们的结果为概括带来了更统一的观点，并打开了几个未来的研究方向。

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

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

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

无奖励强化学习（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中````良好条件''''协变量的问题。

尽管无奖励强化学习勘探阶段的主要目标（RF-RL）是减少具有最小轨迹数量的估计模型中的不确定性时间。目前尚不清楚这种安全的探索要求如何影响相应的样本复杂性，以实现所获得的计划中所需的最佳性。在这项工作中，我们首次尝试回答这个问题。特别是，我们考虑了事先知道安全基线政策的情况，并提出了一个统一的安全奖励探索（甜蜜）框架。然后，我们将甜蜜框架专门为表格和低级MDP设置，并分别开发出算法所构成的表格甜味和低级别甜味。两种算法都利用了新引入的截短值函数的凹度和连续性，并保证在探索过程中以高概率侵犯了零约束。此外，两种算法都可以在计划阶段的任何约束中找到近乎最佳的政策。值得注意的是，算法下的样本复杂性在无限制的对应物中匹配甚至超过最恒定因素的最新情况，这证明安全约束几乎不会增加RF-RL的样本复杂性。