维度诅咒是强化学习（RL）中一个广为人知的问题。在状态空间S和动作空间A都是有限的表格设置中，为了获得具有对生成模型的采样访问的近似最优策略，最小最大最优样本复杂度随|S|×|A|线性缩放，当S或A较大时，这可能会非常大。本文考虑一个马尔可夫决策过程（MDP），它允许一组状态动作特征，可以线性表示（或近似）其概率转移核。我们表明，一旦样本大小超过K（1− γ）3ε2（分别为K（1− γ）4ε2），直至某个对数因子。这里K是特征尺寸，γ∈ （0，1）是MDP的贴现系数。两个样本复杂度边界都是可证明的严格的，我们基于模型的方法的结果与最小值最大下限相匹配。我们的结果表明，对于任意大规模的MDP，当K相对较小时，基于模型的方法和Q学习都是样本有效的，这就是本文的标题。
强化学习（RL）研究马尔可夫决策过程（MDP）中的学习和决策问题。近年来，RL在现实世界决策问题中的应用取得了令人兴奋的进展，如AlphaGo[46，47]和自动驾驶[33]。具体而言，RL的目标是基于序列噪声数据，搜索使累积奖励最大化的最优策略。RL有两种流行的方法：基于模型的方法和无模型的方法。•基于模型的方法首先通过从收集的数据样本中学习概率转移模型来制定经验MDP，然后根据经验MDP估计最优政策/价值函数。•无模型方法（例如Q学习）从样本中学习最优策略或最优（动作）值函数。顾名思义，无模型方法并不试图显式学习模型。一般来说，基于模型的方法具有很大的灵活性，因为在首先学习过渡模型之后，它可以应用于任何其他问题，而不需要接触原始数据样本。相比之下，无模型方法由于其在线性质，通常具有内存效率，可以与环境交互并实时更新估计。本文致力于研究基于模型的RL和Q学习（可以说是最常用的无模型RL算法之一）的样本效率。众所周知，MDP受到维度的诅咒。例如，在状态空间S和动作空间A都是有限的表格设置中，为了在给定对生成模型的采样访问的情况下获得接近最优的策略或值函数，最小最大最优样本复杂度随|S|×|A|[5，2]线性缩放。然而，RL的当代应用程序经常遇到具有非常大的状态和动作空间的环境，而数据收集可能很昂贵，甚至风险很高。这表明，当|S|和|a|较大甚至无穷大时，理论发现和实际决策问题之间存在很大差距。为了弥补上述理论与实践的差距，一个自然的想法是对MDP施加某种结构假设。在本文中，我们遵循[63]中研究的基于特征的线性过渡模型，其中每个状态动作对（s，a）∈ S×A允许K维特征向量φ（S，A）∈ R K表示某些未知矩阵Ψ∈ R|S|×K，对于所有（S，a）都是公共的。该模型包括表格模型和齐次模型，其中状态空间可以划分为K个等价类。假设访问生成模型[31，32]，在这种结构假设下，本文旨在回答以下两个问题：
