我们研究了情景马尔可夫决策过程（MDP）的基于模型的线性函数近似无报酬强化学习。在此设置中，智能体分两个阶段工作。在探索阶段，智能体人与环境相互作用，在没有报酬的情况下收集样本。在规划阶段，智能体人被赋予特定的奖励功能，并使用从勘探阶段收集的样本来学习好的政策。在线性混合MDP假设下，我们提出了一种新的可证明有效算法，称为UCRL-RFE，其中MDP的转移概率核可以通过定义在状态、动作和下一状态三元组上的特定特征映射上的线性函数来参数化。我们证明，为了获得任意奖励函数的ϵ最优策略，UCRL-RFE需要最多采样~O（H5d2 \1013− 2）勘探阶段的事件。这里，H是插曲的长度，d是特征映射的维度。我们还提出了使用伯恩斯坦型奖金的UCRL-RFE的变体，并表明它最多需要采样~O（H4d（H+d）ϵ− 2）以实现ϵ最优策略。通过构造一类特殊的线性混合MDP，我们还证明了对于任何无报酬算法，它至少需要采样~Ω（H2dϵ− 2）集以获得ϵ最优策略。根据对ϵ的依赖性和对d的依赖性，如果H，我们的上界与下界匹配≥ d
在强化学习（RL）中，主体顺序地与环境交互并从中获得奖励。在许多现实世界的RL问题中，奖励功能是手动设计的，以鼓励代理人的期望行为。因此，工程师必须一次一次地改变奖励功能，并训练代理检查它是否达到了预期的行为。在这种情况下，RL算法需要用不同的奖励函数重复执行，因此样本效率低下甚至难以处理。为了应对这一挑战，Jin等人[9]提出了一种新的强化学习范式，称为无奖励探索（RFE），该范式在不使用任何奖励函数的情况下探索环境。详细地说，无报酬RL算法由两个阶段组成。第一个阶段称为探索阶段，算法在不接收奖励信号的情况下探索环境。第二阶段称为规划阶段，在该阶段，算法被赋予特定的奖励功能，并使用第一阶段收集的数据来学习策略。他们已经表明，这种探索范式可以在规划阶段学习一个接近最优的策略，在探索阶段收集多项式集数后，给出任何奖励函数。后续工作[12，14，28]提出了改进的算法，以实现更好或接近最佳的样本复杂度。上述所有工作都集中在表格马尔可夫决策过程（MDP）上，其中状态和动作的数量是有限的。在实践中，状态和动作的数量可能很大，甚至是无限的，因此为了计算的可处理性和泛化，需要函数近似。然而，即使是在最简单的线性函数近似下，对于无报酬探索的函数近似的理解仍然没有得到充分的探索，只有两项值得注意的相关工作[18，27]。具体而言，Wang等人[18]研究了线性MDP[21，10]，其中转移概率和奖励函数都允许线性表示，并提出了一种无奖励RL算法，其中Oe（d 3H6ϵ−2）样本复杂度，其中d是线性表示的维数，H是规划范围，ϵ是所需的精度。他们还证明，如果最优状态动作函数是线性的，那么无报酬探索需要在规划范围H中的指数数量的事件来学习ϵ最优策略。Zanette等人[27]考虑了一类稍大的具有低固有Bellman误差的MDP[26]，并提出了一种具有Oe（d 3H5ϵ−2）样本复杂性。然而，这两项工作都假设奖励函数是一些特征映射上的线性函数。此外，[18]中证明的下界适用于一类非常大的MDP，其中最优状态作用函数是线性的，因此它过于保守，无法告诉线性MDP或相关模型的无报酬探索的信息理论极限。
