多智能体分层强化学习综述（国防科技大学：殷昌盛、杨若鹏、朱巍、邹小飞、李峰）

第15卷第4期 智能系统学报 Vol.15 No.4 2020年7月 CAAI Transactions on Intelligent Systems Jul.2020 D0:10.11992tis.201909027 多智能体分层强化学习综述 殷昌盛，杨若鹏，朱巍，邹小飞，李峰 (国防科技大学信息通信学院，湖北武汉430010) 摘要：作为机器学习和人工智能领域的一个重要分支，多智能体分层强化学习以一种通用的形式将多智能体 的协作能力与强化学习的决策能力相结合，并通过将复杂的强化学习问题分解成若干个子问题并分别解决，可 以有效解决空间维数灾难问题。这也使得多智能体分层强化学习成为解决大规模复杂背景下智能决策问题的 一种潜在途径。首先对多智能体分层强化学习中涉及的主要技术进行阐述，包括强化学习、半马尔可夫决策过 程和多智能体强化学习：然后基于分层的角度，对基于选项、基于分层抽象机、基于值函数分解和基于端到端 等4种多智能体分层强化学习方法的算法原理和研究现状进行了综述：最后介绍了多智能体分层强化学习在 机器人控制、博弈决策以及任务规划等领域的应用现状。 关键词：人工智能；机器学习；强化学习；多智能体；综述；深度学习；分层强化学习：应用现状 中图分类号：TP18 文献标志码：A文章编号：1673-4785(2020)04-0646-10 中文引用格式：殷昌盛，杨若鹏，朱巍，等.多智能体分层强化学习综述.智能系统学报，2020,15(4)：646-655. 英文引用格式：YIN Changsheng,.YANG Ruopeng,.ZHU Wei,,etal.A survey on multi-agent hierarchical reinforcement learning J].. CAAI transactions on intelligent systems,2020,15(4):646-655. A survey on multi-agent hierarchical reinforcement learning YIN Changsheng,YANG Ruopeng,ZHU Wei,ZOU Xiaofei,LI Feng (School of Information and Communication,National University of Defense Technology,Wuhan 430010,China) Abstract:As an important research area in the field of machine learning and artificial intelligence,multi-agent hierarch- ical reinforcement learning(MAHRL)integrates the advantages of the collaboration of multi-agent system (MAS)and the decision making of reinforcement learning(RL)in a general-purpose form,and decomposes the RL problem into sub-problems and solves each of them to overcome the so-called curse of dimensionality.So MAHRL offers a potential way to solve large-scale and complex decision problem.In this paper,we systematically describe three key technologies of MAHRL:reinforcement learning(RL),Semi Markov Decision Process(SMDP),multi-agent reinforcement learning (MARL).We then systematically describe four main categories of the MAHRL method from the angle of hierarchical learning,which includes Option,HAM,MAXQ and End-to-End.Finally,we end up with summarizing the application status of MAHRL in robot control,game decision making and mission planning. Keywords:artificial intelligence;machine learning:reinforcement learning;multi-agent;summary;reinforcement learn- ing;hierarchical reinforcement learning;application status 近年来，以深度学习(deep learning,DL)为核问题上取得了众多超越人类水平的成果，使得 心的智能技术取得了长足的进步山，特别是以深 面向自主认知的智能决策有望得到进一步发展， 度强化学习(deep reinforcement learning,.DRL)为并取得关键性突破。强化学习(reinforcement 代表的智能方法在解决雅达利游戏、棋类博弈对 learning,.RL)作为解决序贯决策问题的重要方法 抗、即时策略游戏(real-time strategy,RTS)等决策 其通过与环境的交互试错来学习策略，恰好契合 了人类的经验学习和决策思维方式，可以有效解 收稿日期：2019-09-10. 基金项目：国家社会科学基金项目(2019SKJC-083), 决样本数据获取难等问题。而单Agent系统无法 通信作者：殷吕盛.E-mail:yincsl989@163.com. 实现多个决策者之间的相互协作或竞争关系，往

DOI: 10.11992/tis.201909027 多智能体分层强化学习综述 殷昌盛，杨若鹏，朱巍，邹小飞，李峰 （国防科技大学 信息通信学院，湖北 武汉 430010） 摘 要：作为机器学习和人工智能领域的一个重要分支，多智能体分层强化学习以一种通用的形式将多智能体 的协作能力与强化学习的决策能力相结合，并通过将复杂的强化学习问题分解成若干个子问题并分别解决，可 以有效解决空间维数灾难问题。这也使得多智能体分层强化学习成为解决大规模复杂背景下智能决策问题的 一种潜在途径。首先对多智能体分层强化学习中涉及的主要技术进行阐述，包括强化学习、半马尔可夫决策过 程和多智能体强化学习；然后基于分层的角度，对基于选项、基于分层抽象机、基于值函数分解和基于端到端 等 4 种多智能体分层强化学习方法的算法原理和研究现状进行了综述；最后介绍了多智能体分层强化学习在 机器人控制、博弈决策以及任务规划等领域的应用现状。 关键词：人工智能；机器学习；强化学习；多智能体；综述；深度学习；分层强化学习；应用现状 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2020)04−0646−10 中文引用格式：殷昌盛, 杨若鹏, 朱巍, 等. 多智能体分层强化学习综述 [J]. 智能系统学报, 2020, 15(4): 646–655. 英文引用格式：YIN Changsheng, YANG Ruopeng, ZHU Wei, et al. A survey on multi-agent hierarchical reinforcement learning[J]. CAAI transactions on intelligent systems, 2020, 15(4): 646–655. A survey on multi-agent hierarchical reinforcement learning YIN Changsheng，YANG Ruopeng，ZHU Wei，ZOU Xiaofei，LI Feng (School of Information and Communication, National University of Defense Technology, Wuhan 430010, China) Abstract: As an important research area in the field of machine learning and artificial intelligence, multi-agent hierarch￾ical reinforcement learning (MAHRL) integrates the advantages of the collaboration of multi-agent system (MAS) and the decision making of reinforcement learning (RL) in a general-purpose form, and decomposes the RL problem into sub-problems and solves each of them to overcome the so-called curse of dimensionality. So MAHRL offers a potential way to solve large-scale and complex decision problem. In this paper, we systematically describe three key technologies of MAHRL: reinforcement learning (RL), Semi Markov Decision Process (SMDP), multi-agent reinforcement learning (MARL). We then systematically describe four main categories of the MAHRL method from the angle of hierarchical learning, which includes Option, HAM, MAXQ and End-to-End. Finally, we end up with summarizing the application status of MAHRL in robot control, game decision making and mission planning. Keywords: artificial intelligence; machine learning; reinforcement learning; multi-agent; summary; reinforcement learn￾ing; hierarchical reinforcement learning; application status 近年来，以深度学习 (deep learning，DL) 为核 心的智能技术取得了长足的进步[1] ，特别是以深 度强化学习 (deep reinforcement learning，DRL) 为 代表的智能方法在解决雅达利游戏、棋类博弈对 抗、即时策略游戏 (real-time strategy, RTS) 等决策 问题上取得了众多超越人类水平的成果[2-6] ，使得 面向自主认知的智能决策有望得到进一步发展， 并取得关键性突破。强化学习 (reinforcement learning，RL) 作为解决序贯决策问题的重要方法[5] ， 其通过与环境的交互试错来学习策略，恰好契合 了人类的经验学习和决策思维方式，可以有效解 决样本数据获取难等问题。而单 Agent 系统无法 实现多个决策者之间的相互协作或竞争关系，往 收稿日期：2019−09−10. 基金项目：国家社会科学基金项目 (2019-SKJJ-C-083). 通信作者：殷昌盛. E-mail：yincs1989@163.com. 第 15 卷第 4 期 智 能 系 统 学 报 Vol.15 No.4 2020 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2020

第4期 殷昌盛，等：多智能体分层强化学习综述 ·647· 往需要多智能体通过协作来求解。多智能体系 馈信号，分别用正负反馈表示这个动作对学习目 统(multi-.agent system,MAS)是当前分布式AI领 标是否有益。Agent则通过不断地试错和反馈 域的研究热点，其主要是通过研究Agent之间的 来不断优化动作选择策略，最终学习到一个有目 协同和交互问题，用以解决复杂实时动态多智能 标导向的策略。 体环境下的任务调度、资源分配、行为协调以及 根据环境模型是否已知，强化学习可分为有 冲突消解等协同问题，但是多智能体会导致动作 模型强化学习和无模型强化学习。若已知环境 空间和状态空间呈指数级增长，带来维度灾难问 状态在智能体动作影响之下的转移规律和反馈， 题m。分层强化学习(hierarchical reinforcement 即状态转移概率函数和奖赏函数已知，则称为有 learning,HRL)采用问题分解并分而治之的思想， 模型强化学习，否则便是无模型强化学习。 是解决大规模强化学习的潜在有效途径1。因 有模型强化学习主要基于动态规划的思想 此，研究基于三者相结合的多智能体分层强化学 采用Bellman方程和Bellman最优方程进行策略 (multi-agent hierarchical reinforcement learning, 迭代和值迭代。无模型强化学习则是基于采样的 MAHRL)使解决未知大规模复杂环境下的智能决 方式与环境进行交互学习，当前主要研究的方法 策问题成为可能。 可以分为3类：基于值函数的强化学习方法、基 作为解决复杂空间下协同决策的重要途径，目 于策略搜索的强化学习方法和基于环境建模的强 前MAHRL技术已经在机器人控制、博弈决策、任 化学习方法。 务规划等领域中得到了大量的研究。本文对MAHRL )基于值函数的强化学习。其核心思想是采 的研究现状和相关应用进行了阐述和探讨。 用函数近似的方法将强化学习模型中的状态值函 1预备知识 数、状态动作值函数或策略函数用一个显性的函 数来表示，常用的近似函数有线性函数近似、决 1.1强化学习 策树近似、核函数近似和神经网络等。其中深度 关于机器学习的研究可以分为3个方向，即有 神经网络是近年来在强化学习值函数近似方面应 监督学习、无监督学习和强化学习。其中强化学 用最为广泛和成功的函数。其中，最为典型的应 习的核心思想是通过Agent与环境的不断交互，以 用开始于20l3年DeepMind团队在NIPS上提出 最大化累计回报为目标来选择合理的行动，这与 的DQN(deep Q-networks)算法，其基于值函数的 人类智能中经验知识获取和决策过程不谋而 泛化逼近方法，有效解决了强化学习的“维数灾难 合io。特别是近年来深度强化学习在以AlphaGo、 问题”，但在Q函数逼近过程中存在不稳定的现 AlphaZero、AlphaStar等为代表的机器智能领域的 象。为解决部分可观察的马尔可夫决策问题， 突破山，进一步展现了强化学习在解决复杂决策 Hausknecht等)提出了基于循环神经网络与强化 问题的能力，成为人工智能研究领域的热点。 学习相结合的DRQN算法，在实验环境中取得了 如图1所示，强化学习的架构主要包括 远优于DQN算法的效果。典型的值函数近似方 Agent和环境两部分，Agent首先对环境状态进行 法还有DDQN、Sarsa、Q-learning61等时序差 感知，然后决定选择采取的动作。 分的强化学习算法，它们虽然在某些实际问题中 状态 取得了不错的效果，但其难以求解动作空间比较 Agent 大和随机性策略问题，以及无法对连续动作空间 问题进行建模等。 态 作 动作 2)基于策略搜索的强化学习。其核心思想是 环 择 器 境 将策略参数化，通过不断修正策略的参数求解最 优策略。Silver等II结合Actor-Critie框架和Q- learning算法提出了确定性策略梯度算法(determ- 学习器 inistic policy gradient algorithms,.DPG),其将策略定 奖赏 状态” 义为一个确定性的策略函数，这样在训练模型 图1强化学习的框架结构 时，就不需要考虑动作空间的大小或是否连续， Fig.1 Framework structure of reinforcement learning 能够提升连续动作空间问题求解中对于梯度的估 Agent的动作会对环境产生影响，其环境状态 计效率和准确性。针对经验回放的深度强化学习 也会发生变化，此时Agent会收到来自环境的反 方法存在对内存和计算能力要求较高的问题

往需要多智能体通过协作来求解。多智能体系 统 (multi-agent system, MAS) 是当前分布式 AI 领 域的研究热点，其主要是通过研究 Agent 之间的 协同和交互问题，用以解决复杂实时动态多智能 体环境下的任务调度、资源分配、行为协调以及 冲突消解等协同问题，但是多智能体会导致动作 空间和状态空间呈指数级增长，带来维度灾难问 题 [7]。分层强化学习 (hierarchical reinforcement learning，HRL) 采用问题分解并分而治之的思想， 是解决大规模强化学习的潜在有效途径[8]。因 此，研究基于三者相结合的多智能体分层强化学 习 (multi-agent hierarchical reinforcement learning， MAHRL) 使解决未知大规模复杂环境下的智能决 策问题成为可能。 作为解决复杂空间下协同决策的重要途径，目 前 MAHRL 技术已经在机器人控制、博弈决策、任 务规划等领域中得到了大量的研究。本文对 MAHRL 的研究现状和相关应用进行了阐述和探讨。 1 预备知识 1.1 强化学习 关于机器学习的研究可以分为 3 个方向，即有 监督学习、无监督学习和强化学习[9]。其中强化学 习的核心思想是通过 Agent 与环境的不断交互，以 最大化累计回报为目标来选择合理的行动，这与 人类智能中经验知识获取和决策过程不谋而 合 [10]。特别是近年来深度强化学习在以 AlphaGo、 AlphaZero、AlphaStar 等为代表的机器智能领域的 突破[11] ，进一步展现了强化学习在解决复杂决策 问题的能力，成为人工智能研究领域的热点。 如 图 1 所示，强化学习的架构主要包 括 Agent 和环境两部分，Agent 首先对环境状态进行 感知，然后决定选择采取的动作。 状 态 感 知 器 动 作 选 择 器 学习器 环 境 Agent 动作 状态 奖赏 状态’ 图 1 强化学习的框架结构 Fig. 1 Framework structure of reinforcement learning Agent 的动作会对环境产生影响，其环境状态 也会发生变化，此时 Agent 会收到来自环境的反 馈信号，分别用正负反馈表示这个动作对学习目 标是否有益[12]。Agent 则通过不断地试错和反馈 来不断优化动作选择策略，最终学习到一个有目 标导向的策略。 根据环境模型是否已知，强化学习可分为有 模型强化学习和无模型强化学习[5]。若已知环境 状态在智能体动作影响之下的转移规律和反馈， 即状态转移概率函数和奖赏函数已知，则称为有 模型强化学习，否则便是无模型强化学习。 有模型强化学习主要基于动态规划的思想， 采用 Bellman 方程和 Bellman 最优方程进行策略 迭代和值迭代。无模型强化学习则是基于采样的 方式与环境进行交互学习，当前主要研究的方法 可以分为 3 类：基于值函数的强化学习方法、基 于策略搜索的强化学习方法和基于环境建模的强 化学习方法。 1) 基于值函数的强化学习。其核心思想是采 用函数近似的方法将强化学习模型中的状态值函 数、状态动作值函数或策略函数用一个显性的函 数来表示，常用的近似函数有线性函数近似、决 策树近似、核函数近似和神经网络等。其中深度 神经网络是近年来在强化学习值函数近似方面应 用最为广泛和成功的函数。其中,最为典型的应 用开始于 2013 年 DeepMind 团队在 NIPS 上提出 的 DQN(deep Q-networks) 算法[6] ，其基于值函数的 泛化逼近方法，有效解决了强化学习的“维数灾难 问题”，但在 Q 函数逼近过程中存在不稳定的现 象。为解决部分可观察的马尔可夫决策问题， Hausknecht 等 [13] 提出了基于循环神经网络与强化 学习相结合的 DRQN 算法，在实验环境中取得了 远优于 DQN 算法的效果。典型的值函数近似方 法还有 DDQN[14] 、Sarsa[15] 、Q-learning[16] 等时序差 分的强化学习算法，它们虽然在某些实际问题中 取得了不错的效果，但其难以求解动作空间比较 大和随机性策略问题，以及无法对连续动作空间 问题进行建模等。 2) 基于策略搜索的强化学习。其核心思想是 将策略参数化，通过不断修正策略的参数求解最 优策略。Silver 等 [17] 结合 Actor-Critic 框架和 Q￾learning 算法提出了确定性策略梯度算法 (determ￾inistic policy gradient algorithms, DPG)，其将策略定 义为一个确定性的策略函数，这样在训练模型 时，就不需要考虑动作空间的大小或是否连续， 能够提升连续动作空间问题求解中对于梯度的估 计效率和准确性。针对经验回放的深度强化学习 方法存在对内存和计算能力要求较高的问题， 第 4 期 殷昌盛，等：多智能体分层强化学习综述 ·647·

·648· 智能系统学报 第15卷 Mnih等1提出了异步梯度下降的深度Actor-Crit- 费的时间步长为固定的单位时间，而在SMDP中 c框架，用于并行执行多个智能体用于神经网络 为变量。设N表示时间步长，则标准MDP的概 控制器的优化，并与单步Q-learning、Sarsa、多步 率转移函数和期望报酬可以被扩展为P(s,Ns,a) Q-learning和Actor-Critic等强化学习算法结合 和R(s,Ns,a)。根据Bellman方程，可以得到确定 实现了对深度神经网络的训练，并取得了更好 策略π下的值函数为Agent执行动作a的立即报 的效果。除此之外还有可信赖域策略搜索算法 酬与转移到后续状态s的折扣累积期望之和，如 TRPO19、价值梯度SVG2o、引导策略搜索算法 式(1)所示： GPs2、近端策略优化算法PPO2四和广义优势估 Vm(s)=R(s,π(s)+ 计算法GAE2]随机等几种典型的基于策略梯度 ∑P,Ms,ry(约 (1) 的方法。 式中：R(s,π(s)》是Agent在状态s下执行动作 3)基于环境建模的强化学习。其核心思想是 π(5)后的期望报酬，不难看出，其整体期望报酬与 通过建立环境模型来产生模拟经验样本。对于某 s、N均相关。 些智能体与环境的交互成本较高的情况，而基于 1.3多智能体强化学习 环境建模的强化学习通过建立环境模型来模拟经 面对大规模复杂背景下决策问题时，单Agent 验样本，可以减少采样次数，或者无需在真实环 系统无法实现多个决策者之间存在相互协作或竞 境中进行采样。Sutton2提出的Dyna框架是一 争的关系。因此，在DRL模型基础上扩展为多 种典型的基于环境建模的强化学习。其基本思想 个Agent之间相互合作、通信及竞争的多Agent 是利用与真实环境产生的经验样本来进行环境模 系统，即多智能体强化学习(multi-agent reinforce- 型的学习，而值函数或者策略函数的学习与更新 ment learning,MARL)。多智能体强化学习示意如 则基于真实样本和环境模型产生的虚拟样本。虽 图3。 然Dyna框架能基于真实样本来进行环境模型学 环境 习，并取得了不错的效果，但其环境模型的建立 联合状态S 联合动作 和真实经验样本和虚拟样本的权衡仍然是制约该 动作a1 Agent 1 {a1,a2,,an} 方法发展的关键难点。 联合奖励 F2. Agent 2 动作a 1.2半马尔可夫决策过程 分层强化学习采用策略分层并分而治之的思 Agent n 动作a。 想，可以有效解决维度灾难问题。策略分层的本 质是基于不同的时间抽象尺度扩展动作集，即基 图3多智能体强化学习示意图 本动作和宏动作，而Aget通过在不同程度的时 Fig.3 Multi-agent reinforcement learning diagram 间抽象尺度上进行学习，进而实现分层控制。而 目前关于MARL的研究可以包括2个方面。 在马尔可夫决策过程(Markov decision process,. 1)多智能体系统研究。当前多智能体系统研 MDP)中，每个动作都是假设在单个时间步完成， 究主要从体系结构、Agent信息交互方式和 并没有考虑决策的时间间隔，所以基于MDP的 Agent冲突消解机制3个方面展开。①体系结构 强化学习无法解决需要多个时间步完成的动作阿， 研究：主要围绕集中式和分散式2种展开研究。 此时就需要引入半马尔可夫决策过程(semi Markov 其中分散式又可以区分为层面式(distributed)与 decision process,.SMDP)模型，如图2所示。 分层式(hierarchical)m。除了基本的分层方式，多 智能体体系结构研究还包括智能体协同和任务分 配机制等。②智能体之间信息交互方式研究：目 前主要有Agent直接通信、信道广播方式、信息黑 板模式等方法。③智能体间冲突消解研究：多智 态 能体系统中冲突矛盾主要包括空间冲突、信息冲 突和任务冲突等。当前消解矛盾方法主要包括集 中控制模块法和主从控制法2种。集中控制模块 图2MDP与SMDP 法通过构建模块来集中规划所有Agent的行动策 Fig.2 MDP SMDP 略，但是会带来通信阻塞问题。主从控制法是指 图2中离散的SMDP其实是MDP的一般化 通过一个中心智能体来统一进行任务分配和行为 过程，即MDP中在状态s下执行一个动作需要花 规划来解决智能体之间的矛盾问题，但由于实时

Mnih 等 [18] 提出了异步梯度下降的深度 Actor-Crit￾ic 框架，用于并行执行多个智能体用于神经网络 控制器的优化，并与单步 Q-learning、Sarsa、多步 Q-learning 和 Actor-Critic 等强化学习算法结合 实现了对深度神经网络的训练，并取得了更好 的效果。除此之外还有可信赖域策略搜索算法 TRPO[19] 、价值梯度 SVG[20] 、引导策略搜索算法 GPS[21] 、近端策略优化算法 PPO[22] 和广义优势估 计算法 GAE[23] 随机等几种典型的基于策略梯度 的方法。 3) 基于环境建模的强化学习。其核心思想是 通过建立环境模型来产生模拟经验样本。对于某 些智能体与环境的交互成本较高的情况，而基于 环境建模的强化学习通过建立环境模型来模拟经 验样本，可以减少采样次数，或者无需在真实环 境中进行采样。Sutton[24] 提出的 Dyna 框架是一 种典型的基于环境建模的强化学习。其基本思想 是利用与真实环境产生的经验样本来进行环境模 型的学习，而值函数或者策略函数的学习与更新 则基于真实样本和环境模型产生的虚拟样本。虽 然 Dyna 框架能基于真实样本来进行环境模型学 习，并取得了不错的效果，但其环境模型的建立 和真实经验样本和虚拟样本的权衡仍然是制约该 方法发展的关键难点。 1.2 半马尔可夫决策过程 分层强化学习采用策略分层并分而治之的思 想，可以有效解决维度灾难问题。策略分层的本 质是基于不同的时间抽象尺度扩展动作集，即基 本动作和宏动作，而 Agent 通过在不同程度的时 间抽象尺度上进行学习，进而实现分层控制。而 在马尔可夫决策过程 (Markov decision process, MDP) 中，每个动作都是假设在单个时间步完成， 并没有考虑决策的时间间隔，所以基于 MDP 的 强化学习无法解决需要多个时间步完成的动作[25] ， 此时就需要引入半马尔可夫决策过程 (semi Markov decision process, SMDP) 模型，如图 2 所示。 时间 MDP SMDP 状 态 图 2 MDP 与 SMDP Fig. 2 MDP & SMDP s 图 2 中离散的 SMDP 其实是 MDP 的一般化 过程，即 MDP 中在状态 下执行一个动作需要花 P(s ′ ,N|s,a) R(s ′ ,N|s,a) π a s ′ 费的时间步长为固定的单位时间，而在 SMDP 中 为变量[26]。设 N 表示时间步长，则标准 MDP 的概 率转移函数和期望报酬可以被扩展为 和 。根据 Bellman 方程，可以得到确定 策略 下的值函数为 Agent 执行动作 的立即报 酬与转移到后续状态 的折扣累积期望之和，如 式 (1) 所示： V π (s) = R¯ ∑ (s, π(s))+ s ′ ,N P(s ′ ,N|s, π(s))γ NV π (s ′ ) (1) R¯ (s, π(s)) s π(s) s ′、N 式中： 是 Agent 在状态 下执行动作 后的期望报酬，不难看出，其整体期望报酬与 均相关。 1.3 多智能体强化学习 面对大规模复杂背景下决策问题时，单 Agent 系统无法实现多个决策者之间存在相互协作或竞 争的关系。因此，在 DRL 模型基础上扩展为多 个 Agent 之间相互合作、通信及竞争的多 Agent 系统，即多智能体强化学习 (multi-agent reinforce￾ment learning, MARL)。多智能体强化学习示意如 图 3。 环境 Agent 1 Agent 2 Agent n 联合奖励 {r1 , r2 , ..., rn} 联合动作 {a1 , a2 , ..., an} 联合状态 St St r1 St r2 St rn 动作 a1 动作 a2 ... 动作 an 图 3 多智能体强化学习示意图 Fig. 3 Multi-agent reinforcement learning diagram 目前关于 MARL 的研究可以包括 2 个方面。 1) 多智能体系统研究。当前多智能体系统研 究主要从体系结构、 Agen t 信息交互方式 和 Agent 冲突消解机制 3 个方面展开。①体系结构 研究：主要围绕集中式和分散式 2 种展开研究。 其中分散式又可以区分为层面式 (distributed) 与 分层式 (hierarchical) [7]。除了基本的分层方式，多 智能体体系结构研究还包括智能体协同和任务分 配机制等。②智能体之间信息交互方式研究：目 前主要有 Agent 直接通信、信道广播方式、信息黑 板模式等方法。③智能体间冲突消解研究：多智 能体系统中冲突矛盾主要包括空间冲突、信息冲 突和任务冲突等。当前消解矛盾方法主要包括集 中控制模块法和主从控制法 2 种。集中控制模块 法通过构建模块来集中规划所有 Agent 的行动策 略，但是会带来通信阻塞问题。主从控制法是指 通过一个中心智能体来统一进行任务分配和行为 规划来解决智能体之间的矛盾问题，但由于实时 ·648· 智 能 系 统 学 报 第 15 卷

第4期 殷昌盛，等：多智能体分层强化学习综述 ·649· 性和灾难空间等问题，其适应性和鲁棒性有待提升。 tion间的调用形成分层控制结构。其中Option根 2)多智能体强化学习策略研究。目前MARL 据先验知识提前确定或者通过学习获得。根据是 的学习策略主要可以分为3类：基于共享、基于 基于马尔可夫或者是半马尔可夫，Option方法又 对策和基于最佳响应的多智能体强化学习。①基 可以分为两类：基于马尔可夫决策过程的Markov- 于共享的MARL:其主要思想是研究动作选择前 Option和基于半马尔可夫决策过程的Semi-Markov- Agent之间的相互交互、信息共享以及值函数更 Option 新方法，基于分布式强化学习提高学习速度，典 Markov--Option<g,π，B>三元组分别代表Op 型算法有状态共享、经验共享、策略共享和建议 tion的入口状态集、内部策略和终止条件。Op 共享等。②基于对策的MARL:其主要思想是以 tion开始执行的前提条件是当前状态属于入口状 对策论为基础，综合考虑所有Agent的值函数，寻 态集，即s二P,其中入口状态集P二S。内部策略 求某种对策下的平衡来选择动作，代表算法有 π一般表示为π：p×A→0,1】，其中A为在入口 Minimax-Q、Nash-Q、WoLF、CE-Q等。③基于最 状态集P上能够执行的基本动作集。终止条件B 佳响应的MARL:其主要思想是在其他Agent无 为基于状态了终止的概率集合B(),一般表示为 论采取何种策略情况下寻求最优策略，算法主要 B:S→[0,1]。因此B(sc)=1一般作为Option任务 依赖于收敛准则和无憾准则，典型算法有PHC、 的子目标状态点sc的终止条件，同时A。可以视 IGA、GIGA、GIGA-WoLF等。 为Markov--Option的一种特例。 Semi-Markov-Option<p,4,B>三元组含义类 2多智能体分层强化学习方法 似。同样其Option开始执行的前提条件ssp,其 基于强化学习的智能决策面临的瓶颈之一是 中入口状态集psS,且其只能包含该Option可能 奖赏延时，如果以最终目标为导向来优化策略， 探索到的所有状态。内部策略为μ：9×O。→ 其带来的维数灾难问题会使算法效率非常低27。 [0,1],其中O。为在入口状态集9上能够执行的基 本动作集。终止条件B为基于状态s终止的概 同时由于单Agent系统无法实现多个决策者之间 率集合B(s),而B(sc)=1通常也是Option任务的 存在相互协作或竞争关系，这就需要引入多智能 子目标状态点sc的终止条件。 体，然而多智能体的参与又会带来维度灾难等问 题。HRL基于任务分层来学习每个子任务的策 针对Option强化学习问题，Precup等29提出 了一种基于多时间步模型的单步模型泛化方法。 略，并将多个子任务的策略组合形成有效的全局 策略，可以有效解决维数灾难问题2。 对于任意Option o,设s(o,s,t)表示在1时刻、状态 s下o被启动，则状态s下Option o获得的累计奖 MAHRL是MARL和HRL相结合的结果。 赏R(s,o)和状态转移概率P(sIs,o)可重新定义为 二者结合有两种思路：一是基于分层来解决MARL R(s,0)= 问题，二是采用多智能体解决HRL问题，所以现 E{,+yT41+…+y-lr4-is(o,s,t月 (2) 有MAHRL可根据采用的HRL方法或者MARL 和 方法等不同角度进行分类。由于目前的研究多集 中于前者，本文从分层强化学习的角度对多智能 P(s'ls,0)= (3) = 体分层强化学习方法进行探讨，即基于选项(op 式中：t为Option o持续的总时间步，对于所有状 tion)、基于分层抽象机(hierarchical of abstract ma- 态seS,P(s,t)为Option o从状态s开始经过T chines,HAM、基于值函数分解(MaxQ value func- 个时间步后终止于状态的概率。 tion decomposition)和基于端到端的(end to end)多 此时Q-Learning的值函数迭代公式为 智能体分层强化学习。 Qk+1(s,o)=(1-a4)Q(,o)+ 2.1基于选项的多智能体分层强化学习 ax[r+y'maxeo.Qr(s',o)] (4) 基于选项的多智能体分层强化学习主要是采 Agent的每次学习执行都是以一个Option终 用Option分层强化学习方法来解决多智能体强 止为前提，故造成其利用率不高，为此Precup 化学习问题。Option是一种典型的分层强化学习 基于Markov-Option提出了一种面向单时间步 方法，其最早由Sutton提出，主要思想是基于选 Q-Learning的Option方法，并证明了其收敛性。 项(Option)的学习任务抽象，其中Option本质上 Tang等u则针对StarCraft游戏问题，根据作战规 为在某状态子空间里完成相应子任务的动作序 则不同，作战要素和动作空间组合不同设计101 列。其中Option本身也视作为一种特殊的动作， 种输入特征向量选项，实现了订单生产的强化 并与基本动作共同构成动作集，通过上下层Op- 学习

性和灾难空间等问题，其适应性和鲁棒性有待提升。 2) 多智能体强化学习策略研究。目前 MARL 的学习策略主要可以分为 3 类：基于共享、基于 对策和基于最佳响应的多智能体强化学习。①基 于共享的 MARL：其主要思想是研究动作选择前 Agent 之间的相互交互、信息共享以及值函数更 新方法，基于分布式强化学习提高学习速度，典 型算法有状态共享、经验共享、策略共享和建议 共享等。②基于对策的 MARL：其主要思想是以 对策论为基础，综合考虑所有 Agent 的值函数，寻 求某种对策下的平衡来选择动作，代表算法有 Minimax-Q、Nash-Q、WoLF、CE-Q 等。③基于最 佳响应的 MARL：其主要思想是在其他 Agent 无 论采取何种策略情况下寻求最优策略，算法主要 依赖于收敛准则和无憾准则，典型算法有 PHC、 IGA、GIGA、GIGA-WoLF 等。 2 多智能体分层强化学习方法 基于强化学习的智能决策面临的瓶颈之一是 奖赏延时，如果以最终目标为导向来优化策略， 其带来的维数灾难问题会使算法效率非常低[27]。 同时由于单 Agent 系统无法实现多个决策者之间 存在相互协作或竞争关系，这就需要引入多智能 体，然而多智能体的参与又会带来维度灾难等问 题。HRL 基于任务分层来学习每个子任务的策 略，并将多个子任务的策略组合形成有效的全局 策略，可以有效解决维数灾难问题[28]。 MAHRL 是 MARL 和 HRL 相结合的结果。 二者结合有两种思路：一是基于分层来解决 MARL 问题，二是采用多智能体解决 HRL 问题，所以现 有 MAHRL 可根据采用的 HRL 方法或者 MARL 方法等不同角度进行分类。由于目前的研究多集 中于前者，本文从分层强化学习的角度对多智能 体分层强化学习方法进行探讨，即基于选项 (op￾tion)、基于分层抽象机 (hierarchical of abstract ma￾chines，HAM)、基于值函数分解 (MaxQ value func￾tion decomposition) 和基于端到端的 (end to end) 多 智能体分层强化学习。 2.1 基于选项的多智能体分层强化学习 基于选项的多智能体分层强化学习主要是采 用 Option 分层强化学习方法来解决多智能体强 化学习问题。Option 是一种典型的分层强化学习 方法，其最早由 Sutton 提出[28] ，主要思想是基于选 项 (Option) 的学习任务抽象，其中 Option 本质上 为在某状态子空间里完成相应子任务的动作序 列。其中 Option 本身也视作为一种特殊的动作， 并与基本动作共同构成动作集，通过上下层 Op￾tion 间的调用形成分层控制结构。其中 Option 根 据先验知识提前确定或者通过学习获得。根据是 基于马尔可夫或者是半马尔可夫，Option 方法又 可以分为两类：基于马尔可夫决策过程的 Markov￾Option 和基于半马尔可夫决策过程的 Semi-Markov￾Option。 < φ, π, β > s ⊆ φ φ ⊆ S π π : φ× Aφ → [0,1] Aφ φ β s ′ β(s ′ ) β : S → [0,1] β(sG) = 1 sG Aφ Markov-Option 三元组分别代表 Op￾tion 的入口状态集、内部策略和终止条件。Op￾tion 开始执行的前提条件是当前状态属于入口状 态集，即 ，其中入口状态集 。内部策略 一般表示为 ，其中 为在入口 状态集 上能够执行的基本动作集。终止条件 为基于状态 终止的概率集合 ，一般表示为 。因此 一般作为 Option 任务 的子目标状态点 的终止条件，同时 可以视 为 Markov-Option 的一种特例。 < φ, µ, β > s ⊆ φ φ ⊆ S µ : φ×Oφ → [0,1] Oφ φ β s ′ β(s ′ ) β(sG) = 1 sG Semi-Markov-Option 三元组含义类 似。同样其 Option 开始执行的前提条件 ，其 中入口状态集 ，且其只能包含该 Option 可能 探索到的所有状态。内部策略为 ，其中 为在入口状态集 上能够执行的基 本动作集。终止条件 为基于状态 终止的概 率集合 ，而 通常也是 Option 任务的 子目标状态点 的终止条件。 ε(o,s,t) R(s,o) P(s ′ |s,o) 针对 Option 强化学习问题，Precup 等 [29] 提出 了一种基于多时间步模型的单步模型泛化方法。 对于任意 Option o，设 表示在 t 时刻、状态 s 下 o 被启动，则状态 s 下 Option o 获得的累计奖 赏 和状态转移概率 可重新定义为 R(s,o) = E { rt +γrt+1 +···+γ τ−1 rt+τ−1|ε(o,s,t) } (2) 和 P(s ′ |s,o) = ∑∞ τ=1 γ τP(s ′ ,τ) (3) τ s ∈ S P(s ′ ,τ) s τ s ′ 式中： 为 Option o 持续的总时间步，对于所有状 态 ， 为 Option o 从状态 开始经过 个时间步后终止于状态 的概率。 此时 Q-Learning 的值函数迭代公式为 Qk+1 (s,o) = (1−αk)Qk (s,o)+ αk [ r +γ τmaxo ′∈Os ′ Qk(s ′ ,o ′ ) ] (4) Agent 的每次学习执行都是以一个 Option 终 止为前提，故造成其利用率不高，为此 Precup[30] 基于 Markov-Option 提出了一种面向单时间步 Q-Learning 的 Option 方法，并证明了其收敛性。 Tang 等 [31] 则针对 StarCraft 游戏问题，根据作战规 则不同，作战要素和动作空间组合不同设计 101 种输入特征向量选项，实现了订单生产的强化 学习。 第 4 期 殷昌盛，等：多智能体分层强化学习综述 ·649·

·650· 智能系统学报 第15卷 综上可知，基于选项的MAHRL本质上是基 的立即奖赏也基于M的立即奖赏来确定。当M 于状态空间，不断寻找子目标的学习过程，其可 的状态不发生变化时，Agent时间步内获得的立 执行时态拓展动作的特点对强化学习摆动期的缩 即奖赏为O,所以立即奖赏也可以理解为Aget时 短和效率提高均有一定的促进作用，但是由于其 间步内的累积奖赏。由此可见，HAM方法是依赖 是基于先验知识确定学习与任务之间的转移，所 于设计者的先验知识，从而为有限马尔可夫决策 以基于选项的分层强化学习在未知环境中的适用 过程M提供一个受约束的策略集。 性还有待提高。 其中reduce(HoM)的最优策略可使用SMDP 2.2基于分层抽象的多智能体分层强化学习 Q-learning方法进行迭代逼近。设Agent在t时刻 基于分层抽象的多智能体分层强化学习主要 进入选择点[se,m,t+T时刻到达选择点[S,m], 采用HAM分层强化学习方法来解决多智能体 则Q-learning算法的迭代更新公式为 强化学习问题。其核心思想是将每个子任务抽象 Q([se,mel,ac)=(1-a)Q ([se:me],ac)+ 为一个基于MDP的随机有限状态机，综合考虑 axr+yT+1+…+y-T+-1+ (5) y'maxQ([se,mel,a)] 当前所在状态和有限状态机的状态来选择不同的 式中Parr等B证明了式(5)以概率1收敛到re 策略。令M=<S,A,R,P>为一个有限MDP,S和 duce(HoM)的最优值函数Q,且与标准Q-learn- A分别为状态集合和动作集合，R:S×A→r为奖 ing算法的收敛条件一致。Kulkarni等B1提出了 赏函数，P:S×A→P(S)为状态转移函数。{H}为 一种分层Q值方法，其通过构造两个层级的算 一个随机有限状态机的集合，其中H,=<S,6,9:>, 法，顶层用于决策，确定下一步的目标，底层用于 S、6、9,分别为H,的状态集、随机转移函数和用 具体行动决策，在Montezuma's Revenge游戏中 于确定H,初始状态的随机函数。 取得了较好的效果。 对于每个状态机，其均包含4种状态类型，即 综上可知，基于分层抽象的多智能体分层强 动作(action)、调用(call)、选择(choice)以及停止 化学习由于对学习类型进行了限定，在一定程度 (stop)。其中在action状态时，会根据状态机的当 上可以简化MDP和提高学习效率，而且由于其 前状态执行一个MDP中的动作；在cal类型的状 只需要部分状态即可确定有限状态机的转移，因 态时，会暂停当前的状态机H,并启动执行另一 此对于环境部分可观测领域，基于分层抽象的 个状态机H,即把H,的状态设置为，(s),其中j MAHRL同样适用。 的值由第i个状态机在时刻1时的状态确定。而 23基于值函数分解的多智能体分层强化学习 choice状态是在当前状态机下随机选择下个状 基于值函数分解的多智能体分层强化学习主 态，并在学习过程中不断进行策略优化。stop状 要是采用Dietterich提出的MaxQ分层强化学习 态则是停止当前状态机的活动并返回调用它的状 方法来解决多智能体强化学习问题。其主要思想 态机，同时Agent基于选择的动作进行状态转移 是将一个马尔可夫决策过程M分解为子任务集 并得到相应的奖赏。在整个运行过程中M若没 {Mo,M1,…,Mn,相应的策略π也可分解子策略集 有选择动作，则保持状态不变。 合{o,π1，…，π，其中π：即为对应M的策略，而所 执行学习时，首先人为确定有限状态机集合， 有子任务形成以M。为根节点的分层任务结构。 然后Agent从一个随机的初始有限状态机开始， 在此分层任务结构中，解决M。所采取的动作包 按照一定的策略对其他有限状态机进行依次调用 括两种情况，即执行基本动作和执行其他子任 并执行。若SH为随机有限状态机集合H的状态 务，执行子任务又依次执行其所需的动作，解决 集，则SH包含Agent从初始有限状态机开始可到 了根任务M。也就解决了任务M。其中每个子任 达的所有状态机。为确保在MDP中可持续获得 务M,均由三元组<π，T,R>组成：π：为子任务策 基本动作，初始状态机中不应含有无action的确 略，用于从M,的子节点中选择子任务（基本动 定性无限环和stop类。 作)：T:为终止谓词，用于将M的状态集合S划分 设HoM为基于有限马尔可夫决策过程M和 为M:策略的活动状态集S:和终止状态集F;R 上述随机有限状态机的集合H组合产生的MDP, 为伪奖赏函数，其仅在学习过程中状态集F:的奖 则其状态集可表示为S×SH,H和M的状态转移 赏函数分配时调用。 概率函数共同确定HoM的状态转移概率函数， 与分层Option方法的值函数类似，分层策略 将HoM中的选择点集合记为reduce(HoM),则re- π基于在子任务上的投影值函数即可确定每个状 duce(HoM)与HoM的优化策略相同。其中M的 态的期望回报值V位，s)。对于每个子任务M,其 基本动作仅依赖于H的action状态，reduce(HoM) 均为离散时间SMDP,设状态集为S:,动作集则为

综上可知，基于选项的 MAHRL 本质上是基 于状态空间，不断寻找子目标的学习过程，其可 执行时态拓展动作的特点对强化学习摆动期的缩 短和效率提高均有一定的促进作用，但是由于其 是基于先验知识确定学习与任务之间的转移，所 以基于选项的分层强化学习在未知环境中的适用 性还有待提高。 2.2 基于分层抽象的多智能体分层强化学习 M =< S,A,R,P > R : S × A → r P : S × A → P(S ) {Hi} Hi =< S i ,δi ,φi > S i δi φi Hi Hi 基于分层抽象的多智能体分层强化学习主要 采用 HAM[32] 分层强化学习方法来解决多智能体 强化学习问题。其核心思想是将每个子任务抽象 为一个基于 MDP 的随机有限状态机，综合考虑 当前所在状态和有限状态机的状态来选择不同的 策略。令 为一个有限 MDP，S 和 A 分别为状态集合和动作集合, 为奖 赏函数， 为状态转移函数。 为 一个随机有限状态机的集合，其中 , 、 、 分别为 的状态集、随机转移函数和用 于确定 初始状态的随机函数。 Hi Hj Hj φi(st) j 对于每个状态机，其均包含 4 种状态类型，即 动作 (action)、调用 (cal1)、选择 (choice) 以及停止 (stop)。其中在 action 状态时，会根据状态机的当 前状态执行一个 MDP 中的动作；在 call 类型的状 态时，会暂停当前的状态机 ，并启动执行另一 个状态机 ，即把 的状态设置为 ，其中 的值由第 i 个状态机在时刻 t 时的状态确定。而 choice 状态是在当前状态机下随机选择下个状 态，并在学习过程中不断进行策略优化。stop 状 态则是停止当前状态机的活动并返回调用它的状 态机，同时 Agent 基于选择的动作进行状态转移 并得到相应的奖赏。在整个运行过程中 M 若没 有选择动作，则保持状态不变。 S H H S H 执行学习时，首先人为确定有限状态机集合， 然后 Agent 从一个随机的初始有限状态机开始， 按照一定的策略对其他有限状态机进行依次调用 并执行。若 为随机有限状态机集合 的状态 集，则 包含 Agent 从初始有限状态机开始可到 达的所有状态机。为确保在 MDP 中可持续获得 基本动作，初始状态机中不应含有无 action 的确 定性无限环和 stop 类。 H S ×S H H H 设 HoM 为基于有限马尔可夫决策过程 M 和 上述随机有限状态机的集合 组合产生的 MDP， 则其状态集可表示为 ， 和 M 的状态转移 概率函数共同确定 HoM 的状态转移概率函数， 将 HoM 中的选择点集合记为 reduce(HoM)，则 re￾duce(HoM) 与 HoM 的优化策略相同。其中 M 的 基本动作仅依赖于 的 action 状态，reduce(HoM) 的立即奖赏也基于 M 的立即奖赏来确定。当 M 的状态不发生变化时，Agent 时间步内获得的立 即奖赏为 0，所以立即奖赏也可以理解为 Agent 时 间步内的累积奖赏。由此可见，HAM 方法是依赖 于设计者的先验知识，从而为有限马尔可夫决策 过程 M 提供一个受约束的策略集。 [sc ,mc] t+τ [ s ′ c ,m ′ c ] 其中 reduce(HoM) 的最优策略可使用 SMDP Q-learning 方法进行迭代逼近。设 Agent 在 t 时刻 进入选择点 ， 时刻到达选择点 ， 则 Q-learning 算法的迭代更新公式为 Qk+1 ([sc ,mc],ac) = (1−αk)Qk ([sc ,mc],ac)+ αk[rt +γrt+1 +···+γ τ−1 rt+τ−1+ γ τmaxQk([sc ′ ,mc ′ ],a ′ )] (5) Q ∗ 式中 Parr 等 [32] 证明了式 (5) 以概率 1 收敛到 re￾duce(HoM) 的最优值函数 ，且与标准 Q-learn￾ing 算法的收敛条件一致。Kulkarni 等 [33] 提出了 一种分层 Q 值方法，其通过构造两个层级的算 法，顶层用于决策，确定下一步的目标，底层用于 具体行动决策，在 Montezuma’s Revenge 游戏中 取得了较好的效果。 综上可知，基于分层抽象的多智能体分层强 化学习由于对学习类型进行了限定，在一定程度 上可以简化 MDP 和提高学习效率，而且由于其 只需要部分状态即可确定有限状态机的转移，因 此对于环境部分可观测领域，基于分层抽象的 MAHRL 同样适用。 2.3 基于值函数分解的多智能体分层强化学习 M {M0, M1,··· , Mn} π {π0, π1,··· , πn} πi Mi M0 M0 M0 M Mi < πi ,Ti ,Ri > πi Mi Ti M S Mi S i Fi Ri Fi 基于值函数分解的多智能体分层强化学习主 要是采用 Dietterich 提出的 MaxQ[34] 分层强化学习 方法来解决多智能体强化学习问题。其主要思想 是将一个马尔可夫决策过程 分解为子任务集 ,相应的策略 也可分解子策略集 合 ,其中 即为对应 的策略，而所 有子任务形成以 为根节点的分层任务结构。 在此分层任务结构中，解决 所采取的动作包 括两种情况，即执行基本动作和执行其他子任 务，执行子任务又依次执行其所需的动作，解决 了根任务 也就解决了任务 。其中每个子任 务 均由三元组 组成： 为子任务策 略，用于从 的子节点中选择子任务 (基本动 作)； 为终止谓词，用于将 的状态集合 划分 为 策略的活动状态集 和终止状态集 ； 为伪奖赏函数，其仅在学习过程中状态集 的奖 赏函数分配时调用。 π V π (i,s) Mi S i 与分层 Option 方法的值函数类似，分层策略 基于在子任务上的投影值函数即可确定每个状 态的期望回报值 。对于每个子任务 ，其 均为离散时间 SMDP，设状态集为 ，动作集则为 ·650· 智 能 系 统 学 报 第 15 卷