这篇文章提出了第一个关于任何表格化情节型马尔可夫决策过程（MDP）中需要样本复杂性的 PAC 识别近似最优策略的实例相关下界，并证明了 PEDEL 算法的样本复杂度接近这个下界。鉴于 PEDEL 计算的复杂性，我们提出了一个关于能否使用计算高效的算法达到我们的下界的开放性问题。

Oct, 2023

本文研究了 $(\epsilon,\delta)-\textit {PAC}$ 场景下的随机赌博机问题，给出了上下界，并提供了一个新的基于 argmax Oracle 的实例最优和计算效率高的算法。

Jul, 2022

该研究提出了一种用于上下文 Bandit 问题的复杂度度量方法，展示了其与最优实例相关遗憾的关系，并给出了新的算法来实现当存在一个最优选择时能够分辨性地进行探索。同时，该研究还在采用函数近似的强化学习问题上提出了新的算法，达到了优化的样本规模。

Oct, 2020

为有限的 Merkov 决策过程中的强化学习提供了更好的基于间隙的遗憾度量方法。

Jul, 2021

本篇论文提出了一种新的理论框架 Uniform-PAC，用于测量强化学习算法的性能，可以为高风险应用程序如医疗保健等提供统计性能保障。该框架与传统的 PAC 框架相比，可以提供高概率的后悔保证，因此形成了一座桥梁，填补了文献中缺少的两个设置之间的空白。针对有限状态的情境马尔科夫决策过程，我们演示了新算法的优点，该算法 Uniform-PAC 并同时实现了最优保障和 PAC 保障，除了地平线因素外。

Mar, 2017

通过引入方差缩减策略，设计了一个记忆高效的算法来解决在线序列化强化学习中的勘探和开发之间的平衡问题，该算法的空间复杂度为 $ O (SAH)$，较以前的算法提高了 $S^5A^3$ 倍的效率。

Oct, 2021

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

Jun, 2020

针对有限时间表格 MDPs 的后悔最小化问题，我们推导了一个新颖的渐近问题相关下限。尽管与先前的工作类似（例如针对遍历 MDPs 的工作），这个下限是一个优化问题的解，但我们的推导表明需要在状态 - 动作对的访问分布上附加一个额外的约束条件，以明确考虑 MDP 的动态性。通过一系列示例，我们提供了我们下界的表征，说明不同的 MDP 可能具有显着不同的复杂性。

Jun, 2021

在本文中，我们考虑了隐式马尔科夫决策过程中强化学习的遗憾最小化问题，我们提出了一个具有局部保证的有效算法，以解决这个问题。

Feb, 2021

本文研究了固定时间段内交互式学习智能体的表现，并从样本复杂度的角度提出了上下 PAC 确定性保证边界，为固定时间段内 MDP 的研究提供了理论上的支持。

Oct, 2015