·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 卷