层级强化学习中Q学习的收敛性与稳定性

《Neurocomputing》：Convergence and stability of q-learning in hierarchical reinforcement learning

　　

• 提出了耦合双时间尺度更新的封建Q学习算法。• 提供了相互依赖的层次强化学习首次收敛性和稳定性证明。• 将层次强化学习与双时间尺度随机逼近理论联系起来。• 将算法结果解释为纳什均衡和斯塔克尔伯格均衡。引言决策架构数十年来在工程和其他领域都发挥了核心作用[1]，例如阿波罗任务的制导、导航与控制[2]、化工厂[3]、智能电网[4]、无人机[5]、推荐系统[6]以及算法[7]。此外，架构在自然界中无处不在，例如神经系统中的多样性使人类能够快速准确地控制感知和运动[8]。强化学习（RL）是一个智能体通过与环境交互学习做出序列决策以最大化累积奖励的框架[9]。决策架构也在强化学习中被提出和研究。层次强化学习（HRL）是强化学习的一个子领域，研究用于决策智能体的层次结构。预期优势包括改进的长期信用分配、迁移学习、可解释性以及现有策略的集成[10]、[11]。HRL中已提出许多方法，例如封建RL[12]、[13]、选项[14]、[15]、MAXQ[16]和HAM[17]。此外，HRL在实践中已被证明是有效的[13]、[18]、[19]、[20]、[21]。尽管人们对HRL的理论理解兴趣日益增加[22]、[23]，但HRL的理论基础相比RL仍然不够成熟。此外，已知在HRL中可能会出现非平稳性问题[18]、[19]。我们的工作的主要目标是通过提出一个具有理论保证的封建Q学习算法来为封建RL理论做出贡献。在两级封建RL算法中，两个策略相互作用。高层策略学习为低层策略设置哪些目标，而低层策略则学习如何实现这些目标。从广义上讲，封建Q学习由两个相互连接的Q学习更新规则组成，这些规则利用从随机过程生成的数据相互影响。为了严格分析这种在随机数据下的交织更新，我们依赖于随机逼近（SA）框架[24]、[25]，特别是其双时间尺度变体（TTSA）[26]。通过利用常微分方程方法[26]、[27]，我们将更新规则研究为耦合动力系统，直接解决非平稳性问题。我们考虑具有有限状态空间和动作空间的无限时间范围马尔可夫决策过程（MDP），并通过通过TTSA的视角分析封建Q学习，我们能够证明更新的收敛性和稳定性。据作者所知，我们的工作首次证明了HRL算法的稳定性和封建Q学习相互依赖更新的收敛性。文献中最接近的工作是[28]、[29]。在[28]中，作者定义了一个高层无限时间范围MDP和一个与高层策略独立的低层级 episodic MDP。假设低层MDP中的收敛性，证明了高层MDP中的收敛性[[28]，定理2]。我们的工作与[28]不同之处在于考虑了两个相互连接的无限时间范围MDP，并进行了耦合双时间尺度分析，证明了更新的收敛性和稳定性。我们的设置可以带来一些好处，例如，很容易考虑在低层无限时间范围问题中的外在奖励，这在实际中被证明是有益的[13]。此外，在我们的框架中，我们不需要假设低层级episodic的持续时间是从几何分布中采样的，这可能导致任意长的集数。[28]设置中的另一个缺点是低层折扣因子的选择与预期集时长的选择相关联。在[29]中，考虑具有收敛的非平稳特征的Q学习和深度RL方法的收敛性扩展了[28]中的工作。我们提出的方法的另一个好处是，通过直接将封建RL与TTSA理论联系起来，可以利用TTSA丰富文献中现有的结果，例如有限时间保证[30]、[31]或能够启用更深层次的多时间尺度[32]。因此，TTSA理论不仅用于建立收敛性和稳定性，还用于通过展示封建RL问题可以严格地在TTSA框架中表述，从而为HRL引入新视角。这是缩小HRL理论与实践差距的重要一步，因为将HRL问题视为TTSA问题可以帮助设计具有理论保证的新高效算法。我们工作的另一项贡献是将HRL问题的博弈论解释形式化。博弈论和强化学习是密切相关的领域，因为两者都涉及最优决策。最著名的联系是博弈论和多智能体强化学习（MARL）[33]之间的联系，因为MARL涉及多个智能体在共享环境中相互作用。值得注意的是HRL和博弈论之间更微妙的联系：尽管原始问题设置仅涉及寻找一个智能体，但我们正在将原始MDP分解为多个级别，因此我们可以将每个级别视为多智能体系统中的一个智能体。我们强调，我们的分析表明更新收敛到一个可以被解释为纳什均衡和斯塔克尔伯格均衡的点，这为博弈论方法应用于HRL打开了大门。本工作的贡献可总结如下：• 我们提出了一种封建Q学习算法，该算法由两个相互作用的无限时间范围MDP组成，并将其分析置于双时间尺度随机逼近（TTSA）框架中。• 通过建立封建RL与TTSA之间的严格联系，我们的框架使得可以使用现有的TTSA工具，包括用于更深层次的有限时间分析和多时间尺度扩展。• 我们证明了耦合Q学习更新的收敛性和稳定性，直接解决了层次强化学习中出现的非平稳性问题。• 我们提供了层次相互作用的博弈论解释，表明极限点可以被视为纳什均衡和斯塔克尔伯格均衡。• 我们进行了数值实验来验证理论结果在实际中的正确性。考虑定义在有限集上的函数，我们用表示无穷范数，即，用表示2-范数，即。地板函数定义为。考虑一个矩阵，其第行第列元素为，我们用表示矩阵的向量化，即将其列堆叠，即。片段：问题表述考虑一个MDP，，其中是有限状态空间，是有限动作空间，是动力学，定义了给定当前状态和动作转移到下一状态的概率，是确定性奖励函数，是折扣因子。强化学习的一般目标是找到一个策略，使得对于每个状态，其中定义为：并且期望根据取得。封建RL通过将扁平策略分解为层次结构来解决MDP，见封建Q学习的收敛性和稳定性保证在本节中，为了解决方程(7)中的问题，我们将提出基于Q学习的更新规则。由于TTSA理论构成我们主要的理论框架，我们将简要回顾其主要元素，并利用其推导出所提出的封建Q学习更新行为的见解。封建Q学习更新和，其中代表迭代次数，将被证明收敛到最优的高层和低层Q函数和方程(7)中的。此外，我们将博弈论解释在本节中，我们强调HRL与博弈论之间的联系。特别是，我们关注所提出的封建Q学习方案，并讨论它如何可以被解释为一个两人博弈，其解在这种特殊情况下既是纳什均衡也是斯塔克尔伯格均衡。在高层和低层MDP中的学习可以被视为一个两人博弈，其中高层玩家试图最大化而低层玩家试图最大化。智能体正在学习数值实验基于(8a)、(8b)中提出的封建Q学习更新，我们在图3所示的Minigrid环境[46]中测试我们的HRL算法。目标是让智能体从始终相同的初始状态（图3中浅蓝色三角形代表初始姿态）进入地图上的特定位置（绿色瓦片）。在每个时间步，智能体可以顺时针转90度、逆时针转90度或向前移动。高层策略从的子集中选择瓦片作为目标。结论与展望我们提出了一种称为封建Q学习的HRL方案，并给出了其收敛性和稳定性的理论结果。据作者所知，这是首次保证层次算法稳定性的工作。HRL典型的非平稳性问题通过源于奇异摄动常微分方程理论的时间尺度分离直接加以解决。算法的动力系统解释使得进行了通用分析，提供了新的理论CRediT作者贡献声明Massimiliano Manenti：撰写——审阅与编辑，撰写——原稿，可视化，验证，软件，资源，项目管理，方法论，调查，正式分析，数据管理，概念化。Andrea Iannelli：撰写——审阅与编辑，验证，监督，资源，项目管理，方法论，资助获取，概念化。生成式AI和AI辅助技术在写作过程中的声明在准备本工作期间，作者使用了ChatGPT来检查语法错误和拼写错误。在使用该工具/服务后，作者根据需要审阅和编辑了内容，并对所发表文章的内容承担全部责任。利益冲突声明作者声明他们没有任何已知的可能影响本论文所报告工作的竞争性经济利益或个人关系。致谢由德国研究基金会（DFG，德国研究基金会）在德国卓越战略-EXC 2075–390740016框架下资助。作者感谢斯图加特模拟科学中心（SimTech）的支持。Massimiliano Manenti是斯图加特大学系统理论与自动控制研究所（IST）的博士生。他在米兰理工大学获得了自动化与控制工程学士学位和硕士学位。他的研究兴趣包括层次强化学习、最优控制和移动机器人。