第4期 殷昌盛，等：多智能体分层强化学习综述 ·651· 每个M:的所有子节点，而转移概率P(s,s,d)代 层抽象学习等。 表对于任意状态s∈S:和M,所有子节点Ma,执行 瓶颈和路标状态法的主要思想是在问题求解 动作a获得的立即奖赏为R(s,a)=V(a,),则每 过程中不断寻找中间点，并将其视为子目标从而 个子任务M:对应的Bellman方程为 实现任务的分解和分层。Menache等提出了一 V*(i,s)=V=(a.s)+ 种基于状态空间分割的瓶颈状态法，其主要基于 ∑P,k.ary6 (6) 计算状态空间割集来寻找状态转移图中的最小流 式中：a=π(s,V(i,s)则是从子任务a结束时的 量边集，并将其视为状态瓶颈（子目标），然后 状态s开始，直到子任务M:完成时的回报值期 Agent学习子策略和策略复用来加速分层学习。 望。其中状态-动作值函数如式(7)所示： 瓶颈和路标状态法使用的前提是该任务具有中间 点或中间阶段，所以其对于任务分段不明显或空 Q(i,s,a=Vm(a,s）+ mx.() (7) 间较大的情况并不适用。 共用子空间法的主要思想是通过寻找策略或 式中右侧第2项称为完成函数： 行动地公共区域实现策略自动分层。Drunnond CG.s=∑.Pd.Hls.dY'maxC(.i.》 等6提出了一种基于值函数梯度的子空间发现 即子任务M。终止后完成子任务M的期望回报 方法，该方法首先基于值函数梯度将相邻状态划 值。因此，状态-动作值函数可以分解成立即奖 分成不同的子空间，然后根据梯度值的高低确定 赏V(a,s)和完成函数C(is,a)两部分，即： 该区域是否存在障碍物，以及根据其是否为局部 O(i,s,a)=V(a,s)+C"(i,s,a) (8) 最大、最小值判断为子空间的出入口点，然后将 设MDP的分层策略π为已知，则执行任务 相关顶点和对应子空间值函数存储起来，最后 M时会向下选择执行子任务M,而执行子任务 Agent基于匹配与比较的形式实现相似情形的快 Ma,时又会继续向下选择执行子任务Ma,不断迭 速学习。共用子空间法使用的前提是该任务的策 代直到最后选择基本动作a.,此时根任务M。中 略或行动空间存在公共区域，同时由于其子空间 状态s的投影值V(O,s)可分解为 的发现与更新是一个不断进行的过程，所以会带 Vm(0,s）=V(an,)+C(an-1,s,an)+…+ 来较大的计算量。 (9) C(a1,s,a2)+C(0,s,a1) 多维状态法的主要思想是基于特征向量和特 式中V(a,)=P(sls,an)R(sls,an),是MaxQ算法 征子集对策略进行划分。H正XQ叨方法是一种基 于因子状态表达的多维状态法，其基于变化快慢 的基础。 将状态变量表示成有序的因子状态表，其中每个 在Dietterich设计的MaxQ-Q学习算法中，若 状态变量为一个包含简单MDP的任务层，MDP 每个子任务M,的子策略都为最优，即可确定 之间则通过瓶颈状态集连通。多维状态法的核心 任务M的递归最优策略为π={πo,π1，…，π}。同 思想是基于特征向量，所以对于特征向量无法表 时，Dietterich也证明了算法在Agent奖赏有界且 示的情况并不适用。 执行有序贪婪策略的情况下能稳定收敛。 马氏空间法的主要思想是采用逐步分解的形 综上可知，与Option、HAM采用单个SMDP 式将状态空间划分成一系列都具有Markov特性 来收敛到最优策略不同，基于MaxQ函数分解的 的子空间。Uther等3提出了一种基于树结构的 多智能体分层强化学习通过建立多个可以同步学 TTree方法，其通过树结构来增加抽象状态的解 习的分层SMDP,利用策略分层结构来缩小每个 析度和层次性，在抽象层中对采用缺省策略或由 Agent的搜索空间，可以有效提高学习效率，同时 用户提供确定策略进行明确，从而通过逐层提高 其微、宏观策略均不需要事先确定，都可以在线 子空间解析度来获取模型的Markov特性。马氏 学习，具有较强的灵活性。但是其同样存在需要 空间法的缺点是对空间分解的解析度要求较高， 提前依靠先验知识进行任务层次划分的问题，对 解析度不合适会导致分层失败。 于环境未知的情况依然具有很大的挑战。 基于神经网络的自动分层抽象学习，其核心 2.4基于端到端的多智能体分层强化学习 思想是利用深度神经网络的学习能力实现策略自 基于端到端的多智能体分层强化学习主要思 动分层。Pierre等B)提出了一种Option-Critie学 想是通过Agent自学实现分层抽象，即任务自动 习方法，其通过深度神经网络来寻找任务之间的 分层，而不是像前面3类是基于人为划分和指定， 边界，并在游戏策略学习领域获得了比普通Deep 典型算法有瓶颈和路标状态法、共用子空间法、 Q Network方法更好的效果。还有研究者按照任 多维状态法、马氏空间法和基于神经网络自动分 务分层和策略学习两项工作分别设计神经网络Mi Pi(s ′ ,τ|s,a) s ∈ S i Mi Ma a Ri(s,a) = V π (a,s) Mi 每个 的所有子节点，而转移概率 代 表对于任意状态 和 所有子节点 ，执行 动作 获得的立即奖赏为 ，则每 个子任务 对应的 Bellman 方程为 V π (i,s) = V π ∑ (a,s)+ s ′ ,τ P π i (s ′ ,τ|s,a)γ τV π (i,s ′ ) (6) a = πi(s) V π (i,s ′ ) a s ′ Mi 式中： ， 则是从子任务 结束时的 状态 开始，直到子任务 完成时的回报值期 望。其中状态−动作值函数如式 (7) 所示： Q π (i,s,a) = V π ∑ (a,s)+ s ′ ,τ P π i (s ′ ,τ|s,a)γ τmaxQ π (i,s ′ , π(s ′ )) (7) 式中右侧第 2 项称为完成函数： C π (i,s,a) = ∑ s ′ ,τ P π i (s ′ ,τ|s,a)γ τmaxQ π (i,s ′ , π(s ′ )) Ma Mi V π (a,s) C π (i,s,a) 即子任务 终止后完成子任务 的期望回报 值。因此，状态−动作值函数可以分解成立即奖 赏 和完成函数 两部分，即： Q π (i,s,a) = V π (a,s)+C π (i,s,a) (8) π M0 Ma1 Ma1 Ma2 an M0 s V π (0,s) 设 MDP 的分层策略 为已知，则执行任务 时会向下选择执行子任务 ，而执行子任务 时又会继续向下选择执行子任务 ，不断迭 代直到最后选择基本动作 ，此时根任务 中 状态 的投影值 可分解为 V π (0,s) = V π (an,s)+C π (an−1,s,an)+···+ C π (a1,s,a2)+C π (0,s,a1) (9) V π (an ,s) = ∑ s ′ P(s ′ |s,an)R(s ′ 式中 |s,an)，是 MaxQ 算法 的基础。 Mi πi M π = {π0, π1,··· , πn} 在 Dietterich 设计的 MaxQ-Q 学习算法中，若 每个子任务 的子策略 都为最优，即可确定 任务 的递归最优策略为 。同 时，Dietterich 也证明了算法在 Agent 奖赏有界且 执行有序贪婪策略的情况下能稳定收敛。 综上可知，与 Option、HAM 采用单个 SMDP 来收敛到最优策略不同，基于 MaxQ 函数分解的 多智能体分层强化学习通过建立多个可以同步学 习的分层 SMDP，利用策略分层结构来缩小每个 Agent 的搜索空间，可以有效提高学习效率，同时 其微、宏观策略均不需要事先确定，都可以在线 学习，具有较强的灵活性。但是其同样存在需要 提前依靠先验知识进行任务层次划分的问题，对 于环境未知的情况依然具有很大的挑战。 2.4 基于端到端的多智能体分层强化学习 基于端到端的多智能体分层强化学习主要思 想是通过 Agent 自学实现分层抽象，即任务自动 分层，而不是像前面 3 类是基于人为划分和指定， 典型算法有瓶颈和路标状态法、共用子空间法、 多维状态法、马氏空间法和基于神经网络自动分 层抽象学习等。 瓶颈和路标状态法的主要思想是在问题求解 过程中不断寻找中间点，并将其视为子目标从而 实现任务的分解和分层。Menache 等 [35] 提出了一 种基于状态空间分割的瓶颈状态法，其主要基于 计算状态空间割集来寻找状态转移图中的最小流 量边集，并将其视为状态瓶颈 (子目标)，然后 Agent 学习子策略和策略复用来加速分层学习。 瓶颈和路标状态法使用的前提是该任务具有中间 点或中间阶段，所以其对于任务分段不明显或空 间较大的情况并不适用。 共用子空间法的主要思想是通过寻找策略或 行动地公共区域实现策略自动分层。Drunnond 等 [36] 提出了一种基于值函数梯度的子空间发现 方法，该方法首先基于值函数梯度将相邻状态划 分成不同的子空间，然后根据梯度值的高低确定 该区域是否存在障碍物，以及根据其是否为局部 最大、最小值判断为子空间的出入口点，然后将 相关顶点和对应子空间值函数存储起来，最后 Agent 基于匹配与比较的形式实现相似情形的快 速学习。共用子空间法使用的前提是该任务的策 略或行动空间存在公共区域，同时由于其子空间 的发现与更新是一个不断进行的过程，所以会带 来较大的计算量。 多维状态法的主要思想是基于特征向量和特 征子集对策略进行划分。HEXQ[37] 方法是一种基 于因子状态表达的多维状态法，其基于变化快慢 将状态变量表示成有序的因子状态表，其中每个 状态变量为一个包含简单 MDP 的任务层，MDP 之间则通过瓶颈状态集连通。多维状态法的核心 思想是基于特征向量，所以对于特征向量无法表 示的情况并不适用。 马氏空间法的主要思想是采用逐步分解的形 式将状态空间划分成一系列都具有 Markov 特性 的子空间。Uther 等 [38] 提出了一种基于树结构的 TTree 方法，其通过树结构来增加抽象状态的解 析度和层次性，在抽象层中对采用缺省策略或由 用户提供确定策略进行明确，从而通过逐层提高 子空间解析度来获取模型的 Markov 特性。马氏 空间法的缺点是对空间分解的解析度要求较高， 解析度不合适会导致分层失败。 基于神经网络的自动分层抽象学习，其核心 思想是利用深度神经网络的学习能力实现策略自 动分层。Pierre 等 [39] 提出了一种 Option-Critic 学 习方法，其通过深度神经网络来寻找任务之间的 边界，并在游戏策略学习领域获得了比普通 Deep Q Network 方法更好的效果。还有研究者按照任 务分层和策略学习两项工作分别设计神经网络， 第 4 期 殷昌盛，等：多智能体分层强化学习综述 ·651·