本文旨在研究在有限状态折扣马尔可夫决策过程中，学习接近最优行为的样本复杂度的上下界，并在假设每个动作导致的下一个状态至多有两个的情况下证明了UCRL算法的新界限，同时还通过更加通用且更加严格的下界加强了之前的工作。这些上下界在对数因子上相吻合。

Feb, 2012

本文提出了一种新的泛化强化学习算法，适用于真实环境属于N个任意模型的情况下。该算法被证明在除O（N log^2 N）步骤之外的大部分情况下都是最优的，并考虑了无限的情况。同时研究表明，紧致性是决定存在统一样本复杂度界限的关键标准，并为有限情况给出匹配的下界。

Aug, 2013

本文提出了一种无模型的算法来学习具有折扣因子的马尔可夫决策过程中的政策，该算法的成功概率为(1-p)，且具有样本复杂度O(SALn(1/p)/(ε^2(1-γ)^3))，其中S是状态数，A是行动数，γ是折扣因子，ε是一个近似阈值

Jun, 2020

本文研究在马尔可夫决策过程中，通过生成模型来识别最优策略，提出了 KLB-TS 算法，并提供了其样本复杂度的渐近保证。

Sep, 2020

本研究讨论在线强化学习问题，探讨了是否能够通过加入一个常数子优性差值的假设来实现有效学习，结果发现即使假设线性实现了最优Q函数，仍然需要指数级别的样本量，进一步证明在线学习和生成模型学习之间存在指数差距。

Mar, 2021

本研究考虑采用生成模型（模拟器）以获取平均奖励 MDP 中的 eps 策略最优性的样本复杂度。

Dec, 2022

本文研究了低秩MDP模型下无奖励强化学习及其算法。首先推导出该问题的最低样本复杂度下限，并提出了 RAFFLE 算法，通过无奖励探索可以在样本复杂度显著改善下找到epsilon-最优策略和epsilon-准确的系统识别。最后，提出了 RAFFLE 的规划算法，可学习到近乎准确的表示，是该环境下首个具有表示学习保证的算法。

Mar, 2023

我们在具有均匀遍历的马尔可夫决策过程（MDP）中，通过建立一个估计器来实现平均奖励MDP的最优策略，其样本复杂度达到文献中的下界，并借鉴了Jin和Sidford（2021）以及Li等人（2020）的算法思想。

Oct, 2023

我们研究了一个基于生成模型的平均回报马尔科夫决策过程（MDP）中学习一个ε-最优策略的样本复杂度，建立了复杂度界限Ω(SA(H/ε^2))。我们的结果在参数S、A、H和ε上是极小极大最优的（最多有对数系数），进一步改进了现有工作，其中要么假定所有策略的混合时间均匀有界，要么对参数有次优的依赖。我们的结果基于将平均回报MDP简化为折扣MDP。为了证明这种简化的最优性，我们对γ折扣MDP进行了改进的界限，显示了在γ≥1-1/H的情况下，采样Ω(SA(H/((1-γ)^2ε^2)))足以在弱通信MDP中学习ε-最优策略，从而规避了适用于一般γ折扣MDP的Ω(SA/(1-γ)^3ε^2)的已知下限。我们的分析以跨度参数为基础，对某些实例相关方差参数进行了上界估计，这些上界比基于MDP的混合时间或直径的估计更紧凑，可能具有更广泛的应用。

Nov, 2023

学习连续空间马尔可夫决策过程中的ε-最优策略问题，在具有光滑Bellman算子的一般类别中，通过使用正交三角多项式特征的简单的扰动最小二乘值迭代，并结合基于谐波分析的新型投影技术，实现了速率最优的样本复杂性。

May, 2024