无奖励强化学习（RL）是一种适用于批量RL设置和存在许多感兴趣的奖励函数的设置的框架。在探索阶段，智能体人在不使用预先指定的奖励功能的情况下收集样本。在探索阶段之后，给出奖励函数，智能体使用在探索阶段收集的样本来计算接近最优的策略。Jin等人[2020]表明，在表格设置中，智能体只需要为无奖励RL收集多项式数量的样本（就数量状态、动作数量和计划范围而言）。然而，在实践中，状态和动作的数量可能很大，因此需要函数近似方案来进行泛化。在这项工作中，我们用线性函数近似给出了无报酬RL的正负结果。我们给出了线性马尔可夫决策过程设置中无报酬RL的算法，其中过渡和报酬都允许线性表示。我们算法的样本复杂度在特征维度和规划范围内是多项式的，并且完全独立于状态和动作的数量。我们进一步给出了在只有最优Q函数允许线性表示的情况下无报酬RL的指数下界。我们的结果暗示了关于无报酬RL的样本复杂度的几个有趣的指数分离。
在强化学习（RL）中，主体与未知环境反复交互，以最大化累积奖励。为了实现这一目标，RL算法必须配备探索机制，以有效地解决具有长视野和稀疏奖励信号的任务。经验上，通过将深度RL方法与不同的勘探策略相结合，取得了大量成功。然而，到目前为止，对RL勘探的理论理解相当有限。在这项工作中，我们研究了Jin等人最近的工作中正式化的无报酬RL设置。[2020]。无奖励设置有两个阶段：探索阶段和规划阶段。在探索阶段，智能体从未知环境中收集轨迹，而没有任何预先指定的奖励功能。然后，在规划阶段，将特定的奖励函数给予智能体，目标是使用在探索阶段收集的样本来为给定的奖励函数输出接近最优的策略。从实际角度来看，该范式特别适用于1）批量RL设置[Bertsekas和Tsitsiklis，1996]，其中数据收集和规划被明确分离，2）存在多个感兴趣的奖励函数的设置，例如约束RL[Achiam等人，2017，Altman，1999，Tessler等人，2018]。从理论角度来看，这种设置将探索问题和规划问题分开，这允许人们以理论原则的方式处理它们，而标准RL设置需要同时处理这两个问题。
