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

Jun, 2020

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

本文提出了一种基于 Primal-Dual π Learning 的方法，利用线性对偶性更新价值与策略向量以逼近无穷时间和折扣因子为 1 的马尔可夫决策过程的最优策略，并给出了复杂度上界，并且这种方法还能应用于有限状态、有限动作空间以及随机转移概率模型下的计算问题，当情况许可下，此方法可以在次线性时间内解决平均奖励最大化的问题。

Oct, 2017

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

Jun, 2012

在平均奖励马尔可夫决策过程中，研究学习一种 ε- 最优策略的样本复杂性，提出了最小化的复杂性边界和匹配的极小化下界，通过将平均奖励 MDP 转化为折扣 MDP 来实现优化，并发展了关于方差参数的上限，结果显示弱通信边界优于基于 MDP 的混合时间或直径的边界。

Mar, 2024

该论文研究利用最近邻回归方法的最近邻 Q 学习算法，从单一样本路径中学习具有连续状态空间和未知转移核的无限期贴现 MDPs 的最优 Q 函数，提供了紧密的有限样本收敛速率分析和样本复杂度。

Feb, 2018

该研究探讨了具有连续状态和动作空间的离散时间贴现马尔可夫决策过程，并解决了从观察到的最优行为中推断成本函数的逆问题。研究首先考虑了完全掌握专家策略的情况，并通过使用职业度量、线性对偶和互补松弛条件来刻画逆问题的解集。为避免平凡解和不适当性，引入了自然线性标准化约束。这导致了一个无限维的线性可行性问题，并对其性质进行了深入分析。其次，采用线性函数逼近器和随机化方法，即场景方法和相关的概率可行性保证，为逆问题提供了 ε- 最优解。对于所需的近似精度，进一步讨论了样本复杂度。最后，针对只有有限一组专家示范和生成模型可供使用的更加现实的情况，给出了使用样本时产生的误差界限。

May, 2024

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

Feb, 2023

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

Oct, 2023