离线或批次加固学习试图使用历史数据来学习近乎最佳的政策，而无需积极探索环境。为了应对许多离线数据集的覆盖范围和样本稀缺性，最近引入了悲观的原则，以减轻估计值的高偏差。在理论上已经研究了基于模型的算法的悲观变体（例如，具有较低置信度范围的价值迭代），但他们的无模型对应物（不需要明确的模型估计）尚未得到充分研究，尤其是在样本方面的研究效率。为了解决这种不足，我们在有限的马尔可夫决策过程中研究了Q学习的悲观变体，并在单极浓缩性假设下表征其样品复杂性，该假设不需要全面覆盖状态行动空间。此外，提出了降低方差的悲观Q学习算法来达到近乎最佳的样本复杂性。总的来说，这项工作突出了与悲观和降低差异一起使用时，在离线RL中无模型算法的效率。

Q-Learning，旨在以无模式的方式学习Markov决策过程（MDP）的最佳Q函数，位于加强学习的核心。当涉及到同步设置时（从每次迭代中从生成模型中从生成模型中汲取独立样本）时，已经对理解Q学习的样本效率进行了实质性进展。考虑一个$ \ gamma $ -discounted infinite-horizo​​ n mdp与状态空间$ \ mathcal {s} $和动作空间$ \ mathcal {a} $：要产生一个entrywise $ \ varepsilon $ - 最佳q函数的克制，最先进的Q-Learning理论需要超出$ \ FRAC {| \ Mathcal {s} || \ mathcal {a} || \ {（1- \ gamma）^ 5 \ varepsilon的示例大小^ {2}} $，它无法匹配现有的最低限度下限。这引起了自然问题：Q-Learning的急剧性复杂性是什么？是Q-Learning可怕的次优吗？本文为同步设置解决了这些问题：（1）当$ | \ mathcal {a} | = 1 $（使q学习减少到TD学习）时，我们证明了TD学习的样本复杂性是最佳的最佳和尺度为$ \ frac {| \ mathcal {s} |} {（1- \ gamma）^ 3 \ varepsilon ^ 2} $（最多到日志系数）; （2）当$ | \ mathcal {a} | \ geq 2 $时，我们解决了q-learning的样本复杂性，按$ \ frac {| \ mathcal {s} || \ mathcal {a} || } {（1- \ gamma）^ 4 \ varepsilon ^ 2} $（最多到日志系数）。我们的理论推出了Q-Leature的严格次优，当$ | \ mathcal {a} | \ geq 2 $，并严格严格估计在q-learning中的负面影响。最后，我们扩展了我们的分析以适应异步Q-Learning（即，与马尔可夫样本的情况），锐化其样本复杂性的地平线依赖性为$ \ frac {1} {（1- \ gamma）^ 4} $。

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

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

The softmax policy gradient (PG) method, which performs gradient ascent under softmax policy parameterization, is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. For $\gamma$-discounted infinite-horizon tabular Markov decision processes (MDPs), remarkable progress has recently been achieved towards establishing global convergence of softmax PG methods in finding a near-optimal policy. However, prior results fall short of delineating clear dependencies of convergence rates on salient parameters such as the cardinality of the state space $\mathcal{S}$ and the effective horizon $\frac{1}{1-\gamma}$, both of which could be excessively large. In this paper, we deliver a pessimistic message regarding the iteration complexity of softmax PG methods, despite assuming access to exact gradient computation. Specifically, we demonstrate that the softmax PG method with stepsize $\eta$ can take \[ \frac{1}{\eta} |\mathcal{S}|^{2^{\Omega\big(\frac{1}{1-\gamma}\big)}} ~\text{iterations} \] to converge, even in the presence of a benign policy initialization and an initial state distribution amenable to exploration (so that the distribution mismatch coefficient is not exceedingly large). This is accomplished by characterizing the algorithmic dynamics over a carefully-constructed MDP containing only three actions. Our exponential lower bound hints at the necessity of carefully adjusting update rules or enforcing proper regularization in accelerating PG methods.

本文通过离线数据在两人零和马尔可夫游戏中学习NASH Equilibria的进展。具体而言，考虑使用$ S $州的$ \ gamma $ discousped Infinite-Horizo​​n Markov游戏，其中Max-player具有$ $ ACTIVE，而Min-player具有$ B $ Actions。我们提出了一种基于悲观模型的算法，具有伯恩斯坦风格的较低置信界（称为VI-LCB游戏），事实证明，该算法可以找到$ \ varepsilon $ - approximate-approximate nash平衡，带有样品复杂性，不大于$ \ frac {c_ {c_ {c_ {c_ { \ Mathsf {剪切}}}^{\ star} s（a+b）} {（1- \ gamma）^{3} \ varepsilon^{2}} $（最多到某个log factor）。在这里，$ c _ {\ mathsf {剪切}}}^{\ star} $是一些单方面剪接的浓缩系数，反映了可用数据的覆盖范围和分配变化（vis- \`a-vis目标数据），而目标是目标精度$ \ varepsilon $可以是$ \ big（0，\ frac {1} {1- \ gamma} \ big] $的任何值。我们的样本复杂性绑定了先前的艺术，以$ \ min \ {a， b \} $，实现整个$ \ varepsilon $ range的最小值最佳性。我们结果的一个吸引力的功能在于算法简单性，这揭示了降低方差降低和样本拆分的不必要性。

本文涉及两人零和马尔可夫游戏 - 可以说是多代理增强学习中最基本的设置 - 目的是学习纳什平衡（NE）的样本 - 优越。所有先前的结果至少都有两个障碍中的至少一个：多种试剂的诅咒和长层的障碍，无论使用采样方案如何。假设访问灵活的采样机制：生成模型，我们朝着解决此问题迈出了一步。专注于非平稳的有限 - 霍森马尔可夫游戏，我们开发了一种学习算法$ \ mathsf {nash} \ text { - } \ mathsf {q} \ text { - } \ text { - } \ mathsf {ftrl} $ and deflavery and Adaptive采样方案对抗性学习中的乐观原则（尤其是跟随规范化领导者（FTRL）方法），具有精致的奖励术语设计，可确保在FTRL动力学下进行某些可分解性。我们的算法使用$$ \ widetilde {o} \ bigg（\ frac {h^4 s（a+b）} {\ varepsilon^2} \ bigg）$ bigg）$ samples $ \ varepsilon $ -Approximate Markov ne策略其中$ s $是状态的数量，$ h $是地平线，而$ a $ a $ a $ a $ a $（resp。〜 $ b $）表示max-player的动作数（分别〜min-player）。从最小的意义上讲，这几乎无法得到解决。在此过程中，我们得出了一个精致的遗憾，以赋予FTRL的遗憾，从而明确说明了差异数量的作用，这可能具有独立的利益。

维度学习（RL）的诅咒是一种广为人知的问题。在表格设置中，状态空间$ \ mathcal {s} $和动作空间$ \ mathcal {a} $均为有限的，以获得与生成模型的采样访问的几乎最佳的政策，最低限度的最佳样本复杂度尺度用$ | \ mathcal {s} | \ times | \ mathcal {a} | $，它在$ \ mathcal {s} $或$ \ mathcal {a} $很大。本文考虑了Markov决策过程（MDP），该过程承认一组状态操作功能，该功能可以线性地表达（或近似）其概率转换内核。我们展示了基于模型的方法（RESP。$〜$ Q-Learning）可否在样本大小超过订单时，通过高概率可以获得高概率的$ \ varepsilon $ -optimal策略（RESP。$〜$ q-function） $ \ frac {k} {（1- \ gamma）^ {3} \ varepsilon ^ {2}} $（resp. $〜$$ \ frac {k} {（1- \ gamma）^ {4} varepsilon ^ {2}} $），直到一些对数因子。在这里，$ k $是特征尺寸和$ \ gamma \ IN（0,1）$是MDP的折扣系数。两个样本复杂性界限都是可透明的，我们对基于模型的方法的结果匹配最低限度的下限。我们的结果表明，对于任意大规模的MDP来说，基于模型的方法和Q-Learning都是在$ K $相对较小的时候进行样本效率，因此本文的标题。

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

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.

我们研究了具有线性函数近似增强学习中的随机最短路径（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）。只要其累积变化不超过某些变化预算，奖励功能和国家过渡功能都可以随时间随时间变化。我们提出了重新启动的Q学习，以上置信度范围（RestartQ-UCB），这是第一个用于非平稳RL的无模型算法，并表明它在动态遗憾方面优于现有的解决方案。具体而言，带有freedman型奖励项的restartq-ucb实现了$ \ widetilde {o}（s^{\ frac {1} {3}} {\ frac {\ frac {1} {1} {3}} {3}} {3}} {3}} {3}} {3}} {3}} {3}} {\ delta ^{\ frac {1} {3}} h t^{\ frac {2} {3}}} $，其中$ s $和$ a $分别是$ \ delta> 0 $的状态和动作的数字是变化预算，$ h $是每集的时间步数，而$ t $是时间步长的总数。我们进一步提出了一种名为Double-Restart Q-UCB的无参数算法，该算法不需要事先了解变化预算。我们证明我们的算法是\ emph {几乎是最佳}，通过建立$ \ omega的信息理论下限（s^{\ frac {1} {1} {3}}} a^{\ frac {1} {1} {3}}}}}} \ delta^{\ frac {1} {3}} h^{\ frac {2} {3}}}} t^{\ frac {2} {3}}} $，是非稳态RL中的第一个下下限。数值实验可以根据累积奖励和计算效率来验证RISTARTQ-UCB的优势。我们在相关产品的多代理RL和库存控制的示例中证明了我们的结果的力量。

政策优化，通过大规模优化技术最大化价值函数来学习兴趣的政策，位于现代强化学习（RL）的核心。除了价值最大化之外，其他实际考虑因素也出现，包括令人鼓舞的探索，以及确保由于安全，资源和运营限制而确保学习政策的某些结构性。这些考虑通常可以通过诉诸正规化的RL来占据，这增加了目标值函数，并通过结构促进正则化术语。专注于无限范围打折马尔可夫决策过程，本文提出了一种用于解决正规化的RL的广义策略镜血压（GPMD）算法。作为策略镜血压LAN的概括（2021），所提出的算法可以容纳一般类凸常规的常规阶级，以及在使用中的规则器的认识到的广泛的Bregman分歧。我们展示了我们的算法在整个学习速率范围内，以无维的方式在全球解决方案的整个学习速率范围内融合到全球解决方案，即使常规器缺乏强大的凸起和平滑度。此外，在不精确的策略评估和不完美的政策更新方面，该线性收敛特征是可透明的。提供数值实验以证实GPMD的适用性和吸引力性能。

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

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

我们研究了随机的最短路径（SSP）问题，其中代理商必须以最短的预计成本达到目标状态。在问题的学习制定中，代理商没有关于模型的成本和动态的知识。她反复与k $剧集的型号交互，并且必须尽量减少她的遗憾。在这项工作中，我们表明这个设置的Minimax遗憾是$ \ widetilde o（\ sqrt {（b_ \ star ^ 2 + b_ \ star）| s | a | a | k}）$ why $ b_ \ star $ a符合来自任何州的最佳政策的预期成本，$ S $是状态空间，$ a $是行动空间。此相匹配的$ \欧米茄（\ SQRT {B_ \星^ 2 | S | |甲| K}）$下界Rosenberg等人的。 [2020]对于$ b_ \ star \ ge 1 $，并改善了他们的遗憾，以\ sqrt {| s |} $ \ you的遗憾。对于$ b_ \ star <1 $我们证明$ \ omega的匹配下限（\ sqrt {b_ \ star | s | a | a | k}）$。我们的算法基于SSP的新颖减少到有限地平线MDP。为此，我们为有限地域设置提供了一种算法，其前期遗憾遗憾地取决于最佳政策的预期成本，并且仅对地平线上的对数。

本文介绍了一项有关离线增强学习中依赖间隙依赖样品复杂性的系统研究。先前的工作显示了何时最佳策略和行为策略之间的密度比上限（最佳策略覆盖范围假设），则代理可以实现$ o \ left（\ frac {1} {\ epsilon^2} \ right）$ rate，这也是最小值的最佳。我们在最佳策略覆盖范围假设下显示，当在最佳$ q $ unction中存在积极的子临时差距时，可以将费率提高到$ o \ left（\ frac {1} {\ epsilon} \ right）$。。此外，我们显示了行为策略的访问概率何时在最佳策略的访问概率为正（统一的最佳策略覆盖范围假设）的状态下，均匀下降，识别最佳政策的样本复杂性独立于$ \ frac {1} {\ epsilon} $。最后，我们呈现几乎匹配的下限，以补充我们的间隙依赖性上限。

我们研究了在随机最短路径（SSP）设置中的学习问题，其中代理试图最小化在达到目标状态之前累积的预期成本。我们设计了一种新型基于模型的算法EB-SSP，仔细地偏离了经验转变，并通过探索奖励来赋予经验成本，以诱导乐观的SSP问题，其相关价值迭代方案被保证收敛。我们证明了EB-SSP实现了Minimax后悔率$ \ tilde {o}（b _ {\ star} \ sqrt {sak}）$，其中$ k $是剧集的数量，$ s $是状态的数量， $ a $是行动的数量，而B _ {\ star} $绑定了从任何状态的最佳策略的预期累积成本，从而缩小了下限的差距。有趣的是，EB-SSP在没有参数的同时获得此结果，即，它不需要任何先前的$ B _ {\ star} $的知识，也不需要$ t _ {\ star} $，它绑定了预期的时间 ​​- 任何州的最佳政策的目标。此外，我们说明了各种情况（例如，当$ t _ {\ star} $的订单准确估计可用时，遗憾地仅包含对$ t _ {\ star} $的对数依赖性，因此产生超出有限范围MDP设置的第一个（几乎）的免地相会遗憾。

以目标为导向的强化学习，代理商需要达到目标状态，同时将成本降至最低，在现实世界应用中受到了极大的关注。它的理论配方是随机最短路径（SSP），在在线环境中进行了深入研究。然而，当禁止使用这种在线互动并且仅提供历史数据时，它仍然被忽略了。在本文中，当状态空间和动作空间有限时，我们考虑离线随机路径问题。我们设计了基于简单的价值迭代算法，以解决离线政策评估（OPE）和离线政策学习任务。值得注意的是，我们对这些简单算法的分析产生了强大的实例依赖性边界，这可能意味着接近最佳的最佳范围最佳范围。我们希望我们的研究能够帮助阐明离线SSP问题的基本统计限制，并激发超出当前考虑范围的进一步研究。

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.