基于区间的平均奖励 MDP 的最优样本复杂度

我们研究了一个基于生成模型的平均回报马尔科夫决策过程（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 的混合时间或直径的估计更紧凑，可能具有更广泛的应用。