我们研究了一个基于生成模型的平均回报马尔科夫决策过程（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 转化为折扣 MDP 来实现优化，并发展了关于方差参数的上限，结果显示弱通信边界优于基于 MDP 的混合时间或直径的边界。

Mar, 2024

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

Oct, 2023

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

Jun, 2018

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

Jun, 2020

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

May, 2024

我们提出了一种名为 LOOP 的新算法框架，它结合了基于模型和基于值的方法，用于研究无限时域平均奖励马尔可夫决策过程（AMDPs）。此外，我们提出了一个新的复杂度度量并证明了框架在几乎所有 AMDPs 中的有效性。

Apr, 2024

提出了一种采用采样技术的快速算法来解决折扣马尔可夫决策过程的近似求解，并证明了算法的收敛性和复杂度。同时，结合经典的价值迭代与方差约减技术，改进了该算法的性能，使其具有线性收敛性和渐进最优性。

Oct, 2017

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

Jun, 2012

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

Feb, 2024