部分可观察性是许多强化学习应用中的一个常见挑战，这需要一个智能体来维持记忆，推断潜在状态，并将这些过去的信息整合到探索中。这一挑战导致了许多用于学习一般部分可观测马尔可夫决策过程（POMDP）的计算和统计困难结果。这项工作表明，这些硬度障碍并不妨碍对丰富有趣的POMDP子类进行有效的强化学习。特别是，我们提出了一种样本有效算法OOM-UCB，用于情景有限欠完备POMDP，其中观察的数量大于潜在状态的数量，并且探索对于学习至关重要，从而将我们的结果与先前的工作区分开来。OOM-UCB实现了~O（1/ε2）的最优样本复杂度，用于找到ε-最优策略，并且在所有其他相关量中都是多项式。作为一个有趣的特例，我们还为具有确定性状态转换的POMDP提供了一种计算和统计有效的算法。
在许多顺序决策设置中，代理缺乏关于系统底层状态的完整信息，这一现象被称为部分可观测性。部分可观测性使强化学习和规划的任务显著复杂化，因为观测的非马尔可夫性质迫使主体在探索收集环境信息的同时，保持对系统状态信念的记忆和推理。例如，由于遮挡，机器人可能无法感知环境中的所有对象，必须考虑这些对象如何移动以避免碰撞[10]。类似的推理问题出现在不完全信息游戏[8]、医疗诊断[13]和其他[25]中。此外，从理论角度来看，众所周知的复杂性理论结果表明，在部分可观察的环境中学习和规划通常在统计和计算上都是困难的[23，22，30，21]。具有部分可观测性的强化学习的标准公式是部分可观测马尔可夫决策过程（POMDP），在该过程中，基于噪声观测的代理做出影响潜在状态演化的决策。复杂度障碍适用于该模型，但它们是最坏的情况，并且不排除POMDP的有趣子类的有效算法。因此，我们要求：
最近的工作[3，12]研究了这一问题，该工作将决策组件纳入了一系列关于潜在变量模型[14，29，2，1]（包括隐马尔可夫模型）中估计的“谱方法”的工作中。简言之，这些估计结果基于矩量法，表明在某些假设下，模型参数可以通过低阶矩张量的分解来计算。Azizzadenesheli等人[3]和Guo等人[12]的工作在POMDP设置中使用张量分解，并获得样本效率保证。这两个结果都没有考虑到战略探索对于信息获取至关重要的环境，也没有解决更一般的强化学习问题中的核心挑战之一。我们的贡献。在这项工作中，我们提供了新的样本有效算法，用于欠完备状态下有限POMDP中的强化学习，其中观察数大于潜在状态数。这一假设在潜在变量模型中的估计文献中是相当标准的[1]。我们的主要算法OOM-UCB使用乐观原则进行探索，并使用所收集的信息来估计由环境引起的可观测算子。我们的主要结果证明，OOM-UCB使用具有所有相关参数和发射矩阵的最小奇异值的多项式缩放的多个样本，为POMDP找到了接近最优的策略。值得注意的是，OOM-UCB在O（1/ε2）的最优速率下找到了ε-最优策略。
