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

Feb, 2012

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

Jun, 2012

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

Jun, 2020

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

Dec, 2022

本文主要针对利用线性函数逼似模型来评估折扣无限领域MDP中的策略的问题，研究两种广泛使用的政策评估算法（TD和TDC）最佳线性系数的预估误差所需的样本复杂度，提出了一个高可靠性收敛保证的样本复杂度上界，并且在策略内和策略外设置中都达到了最优容差级别依赖，同时，通过显示与问题相关的量，表明在策略内设置中，我们的上界与关键问题参数的Minimax下界相匹配，包括特征映射的选择和问题维数。

May, 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

我们研究了强化学习问题中的约束马尔可夫决策过程（CMDP），并通过优化算法对CMDP问题的样本复杂度提出了改进，实现了优化的问题相关保证。

Feb, 2024

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

May, 2024

我们回顾平均奖励马尔可夫决策过程（MDP）中 ε-最优策略的识别，并提出了一种新算法，在小 ε 范围内其样本复杂度为 SAD/ε^2；此外，我们还提出了一种在线算法，其样本复杂度为 SAD^2/ε^2，并且提出了一种有前景的基于数据相关的停止准则的新方法以进一步减小此样本复杂度界限。

May, 2024