分层强化学习（HRL）方法有望在统计和计算效率方面为顺序决策问题提供更有效的解决方案。尽管这一点已经在各种任务中得到了经验性的证明，但量化这种方法的好处的理论结果仍然很少。在本文中，我们讨论了马尔可夫决策过程中产生高效HRL方法的结构类型。具体而言，我们形式化了HRL可以利用重复性好的“subMDP”的直觉，具有类似的奖励和过渡结构。我们表明，在合理的假设下，利用这种结构的基于模型的汤普森抽样式HRL算法在统计上是有效的，这是通过有限时间后悔界限建立的。我们还建立了具有结构诱导选项的规划接近最优且计算效率高的条件。
分层强化学习（HRL）是指主体在多个时间抽象层次上行动和计划的能力[Sutton等人，1999，Barto和Mahadevan，2003]。原则上，这种能力可以带来几个好处：（1）更有效的探索，通过采用有助于代理人更有效地在国家空间内流通的政策；（2） 更有效的信用分配，因为时间扩展模型在许多时间步骤上传播信用，并且可以重复使用相同的数据流来了解许多可能的偶然事件（例如，表示为子目标）；以及（3）在新情况下快速解决较小问题并构建相应策略和模型的能力。从理论角度来看，（1）已在最近的工作中进行了研究[Fruit等人，2017]。方面（2）和（3）在大量论文中得到了实证验证，但没有太多理论分析，除了一些特殊情况，如Mann等人的工作。[2015]。在本文中，我们给出了两个一般结果，它们突出了HRL在规划速度和统计效率方面有望带来益处的问题类型。首先，正如过去的经验所强调的那样，在马尔可夫决策过程（MDP）中具有重复的结构可以导致两方面的大加速。第二，在规划方面，当我们能够“隔离”可以单独解决的井子问题，然后将其解决方案“缝合”在一起时，HRL提供了好处。我们将后一种直觉形式化。贡献：首先，我们使用状态划分将MDP分解的概念形式化为子问题。其次，我们通过扩展Osband et al.[2013]中的结果，建立遗憾界限，将次优规划导致的错误与学习导致的错误分离开来，从而证明了环境中分层结构的存在可以导致统计上有效的学习。如果原始MDP可以分解为相对较小的重复问题，则可以显著减少后验采样探索算法的预期遗憾。最后，我们研究了原始问题分解下的规划问题。我们建立了规划的复杂性与解决子问题的意外事件数量之间的关系，并通过出口轮廓的概念进行了形式化。我们正式表明，如果原始问题可以被划分为小且分离良好的重复问题，则可以更快地获得接近最优的规划。
