本文使用生成模型证明了在马尔可夫决策过程中，基于值迭代算法的样本复杂度PAC上限为O(Nlog(N/δ)/((1-γ)³ε²))，其中N为状态-动作对的数量，γ为折扣因子，ε表示动作价值函数的ε-最优估计，δ为概率。同时证明了在任何强化学习算法中，基于每个状态-动作对估计最优动作值函数的样本复杂度下限为Θ(Nlog(N/δ)/((1-γ)³ε²))，该上限和下限在N，ε、δ、1/(1-γ)方面匹配。

Jun, 2012

本文提出一种基于UCB探索策略的Q学习算法并将其应用于无限时间序列的马尔可夫决策问题，实验结果表明算法的探索样本复杂度的上限为O（SA/ε²(1-𝛾)⁷），此外该算法还可提高之前深度Q学习的表现。

Jan, 2019

该研究通过异步Q-learning算法，在马尔科夫决策流程中的样本轨迹中学习最优动作价值函数，给出了基于L∞的样本复杂度分析及等式组，并在此基础上提出一种新的方差缩减技术，进一步提高了算法的效率。

Jun, 2020

本文研究了在强化学习中常用的 Q-learning 算法，在理论和实践之间的差距，并提出了两种改进方法，分别为 Q-Rex 和 Q-RexDaRe，这两个方法能够更有效地找到线性马尔科夫决策过程的最佳策略并提供了采样复杂度的非渐近界限。

Oct, 2021

本文研究了利用目标网络解决深度强化学习Q学习算法在非目标策略情况下发散的问题，使用生成式神经模型研究了其样本复杂度，发现目标学习算法的样本复杂度是以1-γ为主导的，并且证明了引入周期性目标Q函数网络不会牺牲样本复杂度。

Mar, 2022

本文提出了一种无需进一步探索的离线强化学习方法，通过精心设计的模型实现了最优的样本复杂度，适合处理数据分布转移和数据覆盖范围受限的情况。

Apr, 2022

本文论述了基于核心回归的Q学习在存在生成模型时的采样复杂度，提出了一种非参数Q学习算法，其样本复杂度优化到ε和核心复杂度的阶数，这是针对这种普遍模型的首个具有有限样本复杂度的结果。

Feb, 2023

本论文提出了两种模型无关的算法，分别是分布鲁棒的Q-learning及其方差缩减的版本。这些算法可在处理分布移位时有效地学习强大的策略。在一系列数值实验中，这些算法的理论发现和效率得到了证实。

May, 2023

本文研究在线强化学习的样本复杂性问题，并考虑了有关系统动态的部分知识，提出了一种基于Q-learning的算法，能够在具有有限Markov决策过程的系统中实现近似最优策略。

Dec, 2023

通过理论分析和实证评估，本文探讨了当集成模型为基础的方法时，$Q$-学习在样本复杂度方面相对其无模型对应物而言的样本效率的条件。

Feb, 2024