我们研究了一个基于生成模型的平均回报马尔科夫决策过程（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

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

Dec, 2022

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

Oct, 2023

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

May, 2024

我们提出了多种经过证明有效的无模型强化学习算法，包括基于参考优势分解的在线无模型强化学习算法以及适用于模拟器环境的无模型强化学习算法，在平均报酬马尔科夫决策过程中实现更好的折扣估计和置信区间的高效构建。

Jun, 2023

通过生成采样模型计算马尔可夫决策过程问题的最优策略及其样本复杂度分析。

Jun, 2018

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

Jun, 2020

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

May, 2024

本研究提出了一种政策优化算法，用于处理成本约束下的无限时间跨度平均奖励马尔可夫决策过程中的后悔最小化问题，该算法在符合一定条件的 MDP 下具有较低的后悔度和约束违反率，并将其推广到弱通信 MDP 领域，为该领域提供了复杂度可行的算法。

Jan, 2022

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

Oct, 2015