本文使用生成模型证明了在马尔可夫决策过程中，基于值迭代算法的样本复杂度PAC上限为O(Nlog(N/δ)/((1-γ)³ε²))，其中N为状态-动作对的数量，γ为折扣因子，ε表示动作价值函数的ε-最优估计，δ为概率。同时证明了在任何强化学习算法中，基于每个状态-动作对估计最优动作值函数的样本复杂度下限为Θ(Nlog(N/δ)/((1-γ)³ε²))，该上限和下限在N，ε、δ、1/(1-γ)方面匹配。
Jun, 2012
本研究提出了基于随机游走探索的Q学习的问题特定样本复杂度界限，该界限依赖于多个结构性质，并将理论结果与某些经验基准领域相关联，以说明我们的界限在这些领域中是否具有多项式样本复杂度并与经验绩效相关。
May, 2018
研究强化学习的样本效率，证明了两种算法的最小最优性，同时实现了目标准确率的最小最优样本复杂度，这是目前首次提供涵盖整个样本范围的最小最优保证。
May, 2020
本文介绍了在具有线性函数表示的情况下，在折扣无限时间MDPs中分别对策略和目标策略的价值进行估计时，即使存在实现性并观察到精确奖励和转移函数以及为问题类提供最佳先验数据分布，也派生出指数的信息论下限，并引入了一个新的“oracle+ batch algorithm”框架来证明适用于每个分布的底限。工作显示了批处理和在线强化学习之间的指数分离。
Dec, 2020
本文针对强化学习中的大状态空间问题，研究使用函数逼近的强化学习方法，并提出了寻找高效率算法的方案，同时探讨了计算难度与统计问题之间的关系。
Feb, 2022
本研究针对离线强化学习中的样本利用效率问题，提出了基于地位结构的重要性采样（MIS）的悲观算法，并利用较弱的函数逼近前提给出保证。
Mar, 2022
本文提出了一种无需进一步探索的离线强化学习方法，通过精心设计的模型实现了最优的样本复杂度，适合处理数据分布转移和数据覆盖范围受限的情况。
Apr, 2022
本文提出了一种分布式抗干扰强化学习算法，即Robust Phased Value Learning算法，该算法针对四种不同的差距度量指标的不确定性集合进行求解，得到的结果在样本复杂度方面比现有结果具有更好的一致性。
Mar, 2023
在线强化学习中的数据效率是一个核心问题，本文针对有限时间不均匀马尔可夫决策过程，证明了一种修改版的单调值传播算法在理论上达到了最小化遗憾度的最优性，并且没有任何预烧成本，其样本复杂度也是最优的。
Jul, 2023
我们提出了一个新颖的基于后验采样的离线RL算法，该算法在样本效率方面表现出与基于版本空间和经验正则化的算法可比拟的性能，并且具有频率主义的亚优性界限。
Jan, 2024