0 引言

强化学习一般用来解决这样的问题：一个可以感知周围环境的智能体Agent，通过学习来选择要达到目标的最佳动作。通过Agent与环境的交互和不断试错，最终得到完成目标的最佳策略^[1]。强化学习在人工智能领域有着广泛的应用，被认为是设计智能系统的核心技术之一^[2]。近年来提出的深度强化学习，即是将强化学习的决策能力与深度学习的感知能力相结合，为复杂系统的感知决策问题提供了新的思路，并在棋类博弈游戏中取得了显著的成果^[3]。但是，强化学习方法一直受到“维数灾难”的困扰，即学习参数的个数随着状态和动作维数的增加呈指数级增长。为了减小“维数灾难”对强化学习的影响，研究者们将分层、抽象等机制引入强化学习中, 其基本思想是对状态空间进行降维，将复杂的强化学习问题分解为多个具有层次关系的子任务，并在较小的低维空间中逐步解决子任务。

建立在合理的抽象基础上的分层强化学习可以显著减小存储空间和计算量，提高学习速度。目前，主要的分层强化学习方法有Option算法^[4]、MAXQ算法^[5]、层次抽象机 (Hierarchies of Abstract Machine, HAM) 算法^[6]。但是，这些典型的算法都有一个同样的问题，就是均需要利用先验知识来构造任务的层次结构。而在实际应用中，学习环境和学习任务的层次结构有时是未知的，如果依靠专家知识来划分任务层次，会花费巨大的人力，也无法满足在动态未知环境下的应用要求。因此，国内外的研究者都致力于解决分层强化学习的自动分层问题，并且提出了各自的方法。Hengst^[7]提出的HEXQ方法按照状态变量的改变次数进行排序，并认为经常改变的状态变量与低层的子任务有关，改变次数少的变量与高层子任务有关。McGovern^[8]和Stolle^[9]则通过寻找瓶颈状态来划分子任务。Mehta等^[10]提出HI-MAT (Hierarchy Induction via Models And Trajectories) 方法，利用动态贝叶斯网络 (Dynamic Bayesian Network, DBN) 和一条已知的成功轨迹，通过分析动作间的因果关系，构建出一条带因果注释轨迹 (Causally Annotated Trajectory, CAT)，并在CAT上划分出子任务的层次。石川等^[11]提出利用单向值识别出瓶颈状态，以此构造Option，并应用Option算法寻找最佳策略；但是，基于状态进行自动分层的方法，在状态空间没有明显的瓶颈状态时或者状态空间产生变化时，效果并不理想。此外，沈晶^[12]提出OMQ算法，在MAXQ算法的学习过程中针对粗粒度的子任务自动构造Option，并将Option作为子任务插入到MAXQ任务图中，使任务图细化，提升了算法的学习效果；不过对于初始的任务图，仍然需要根据先验知识人工构造。

本文在已有研究的基础上，提出一种适用于MAXQ学习方法的自动分层算法, 该算法根据不同动作执行次数和所影响状态之间的差异，自动构造出任务图; 同时为了使用MAXQ算法对该任务图进行学习，提出了一种新的判断子任务是否结束的方法。

1 马尔可夫决策过程与分层强化学习 1.1 马尔可夫决策过程

一个强化学习系统的基本框架由环境和智能体Agent两部分组成，Agent与环境进行交互。Agent感知到环境的当前状态，然后通过一个策略选择合适的动作去执行。环境对执行的动作作出响应，更新状态并回馈给Agent一个奖励。对于Agent来说，主要目标是努力地使自己在与环境的交互中积累尽可能多的奖励。在强化学习的研究中，一般假设学习任务满足马尔可夫性，将其形式化为马尔可夫决策过程 (Markov Decision Process, MDP)^[13]，一个MDP可以表示为一个四元组〈S, A, P, R〉。其中：S表示环境状态的集合；A表示Agent可以执行的动作的集合；P表示状态转移概率，即Agent执行动作a后，环境状态从s转移到另一个状态s′的概率，记为P(s′|s, a)；R为回报函数，在某个状态s下，当Agent执行一个动作a后，使得环境状态发生改变，此时Agent会从环境得到一个回报值，记为R(s, a)。此外，策略用π表示，MDP中的策略可以视为一个从状态空间到动作空间的映射，在环境状态s下，由策略π决定执行的动作a，记为a=π(s)。

马尔可夫决策的一般过程可以描述为：Agent在状态s下根据策略π决定执行动作a，在完成动作a后，环境状态以概率P(s′|s, a) 改变为s′，Agent得到一个奖赏值r=R(s, a)。强化学习的目标是寻找一个策略，使Agent在完成目标时所获得的累积回报最大。为了确定最优策略, 通常使用值函数V^π(s) 表示在状态s处执行策略π的累积期望回报。值函数可以写为式 (1) 的形式：

$ {V^\pi }\left( s \right) = {E_\pi }\left\{ {{r_t}|{s_t} = s} \right\} = {E_\pi }\left\{ {\sum\limits_{k = 0}^\infty {{\gamma ^k}{r_{t + k + 1}}} |{s_t} = s} \right\} $

(1)

其中: γ为折扣因子，r_t表示t时刻环境状态改变后Agent所得到的回报。由于状态转移的随机性, 在状态s下，策略π的值函数可以定义如下：

$ {V^\pi }\left( {{s_t}} \right) = {r_t} + \gamma \sum\limits_{{s_{t + 1}} \in S} {P\left( {{s_{t + 1}}|{s_t}, \pi \left( {{s_t}} \right)} \right)} {V^\pi }\left( {{s_{t + 1}}} \right) $

(2)

其中: r_t表示Agent获得的直接回报，$ \gamma \sum\limits_{{s_{t + 1}} \in S} {P({s_{t + 1}}|{s_t}, \pi ({s_t})){V^\pi }({s_{t + 1}})} $表示在下一个时刻对于所有可能状态的期望回报。根据Bellman等式，至少有一个最优策略使得值函数最大，在下文中用V^*表示最大的值函数，π^*表示最优策略，强化学习的目标就是寻找到最优策略π^*。期望累积回报和可以用Q函数计算，Q函数又称为状态-动作对值函数，其定义如下：

$ {Q^\pi }\left( {{s_t}, {a_t}} \right) = {r_t} + \gamma \sum\limits_{{s_{t + 1}} \in S} {P\left( {{s_{t + 1}}|{s_t}, {a_t}} \right)} {Q^\pi }\left( {{s_{t + 1}}, {a_{t + 1}}} \right) $

(3)

式 (3) 表示在遵循策略π时，在状态s_t执行动作a_t所得到的期望累积回报。Q函数的形式与值函数类似，同样也满足Bellman等式，也就是说存在最优策略π^*，使得Q值最大。

由于MDP会忽略决策过程的时间间隔，基于MDP的强化学习都假设动作在单个时间步完成，因而无法处理需要多个时间步完成的动作。由于分层强化学习会对原始问题进行抽象，可执行的动作会被替换为需要多个时间步完成的宏动作。为了表示动作执行的时间过程，需要引入半马尔可夫决策过程 (Semi-Markov Decision Process, SMDP)^[14]。SMDP可以视为MDP一种拓展，图 1展示了MDP与SMDP的区别。

MDP中离散事件之间只会间隔同样大小的单个时间步，SMDP的事件之间则有不同大小的时间间隔。根据时间类型不同，SMDP又可以分为离散时间SMDP与连续时间SMDP。以离散时间SMDP为例，时间间隔为时间步的整数倍，用N表示时间步的数量，在SMDP中值函数与Q函数可以写为如下形式：

$ {V^\pi }\left( s \right) = R\left( {s, a} \right) + {\gamma ^N}\sum\limits_{s', N} {P\left( {s', N|s, \pi \left( s \right)} \right)} {V^\pi }\left( {s'} \right) $

(4)

$ {Q^\pi }\left( {s, a} \right) = R\left( {s, a} \right) + {\gamma ^N}\sum\limits_{s', N} {P\left( {s', N|s, a} \right)} {Q^\pi }\left( {s', a'} \right) $

(5)

1.2 分层强化学习

分层强化学习对普通的强化学习进行抽象处理，常用的抽象方法可以分为状态抽象^[15]、时态抽象^[4]和状态空间分解^[16]三类。状态抽象方法是对高维的状态空间，根据所要达到的目标，忽略与当前问题无关的状态分量，使原始状态空间缩小。时态抽象方法将单次执行的基本动作拓展为需要多个时间步执行的抽象动作，Agent从需要考虑每个时间步所执行的动作转变为只需要考虑抽象动作，在当前的抽象动作执行完后再考虑下一个执行的抽象动作，减少了决策次数。状态空间分解是将原始的状态空间分解为多个子空间，Agent在这些子空间中寻找各自的策略，由于子空间规模较小使得Agent更容易找到最优策略。

目前典型的分层强化学习方法有Option、HAM、MAXQ三种。Option方法的基本思想是将学习任务抽象为若干Option，每个Option都是一个为完成子任务而定义在状态空间上的动作序列。这些Option作为一种抽象动作加入到原来的动作集中，Option内部可以使用普通的强化学习方法决定最优的动作执行序列，Agent只需决定执行哪一个Option，简化了问题复杂度。HAM方法将一个MDP过程分解为多个子任务，并将子任务抽象为随机有限状态机，每个随机有限状态机都有自己的内部状态，根据当前随机有限状态机所处的内部状态可以执行动作、改变内部状态、调用别的随机有限状态机或者返回调用自己的随机有限状态机。MAXQ方法将原始学习任务M分解为多个子任务{M₀, M₁, M₂, M₃, …}，策略π也被分解为{π₀, π₁, π₂, π₃, …}，其中π_i为子任务M_i的策略。子任务被分为两类：最基本的是原子型子任务，这类任务无法再被分解，其内部只含有一个可以被执行的基本动作，该动作属于原始学习任务的动作集合。第二类是复合型子任务，其内部含有多个子任务，这些子任务可以是复合型也可以是原子型子任务。所有的子任务组成了一个以M₀为根节点的层次结构，这个层次结构被称为任务图。在任务图中必须先解决下层子任务，上层子任务才会被解决，M₀完成后整个学习任务就完成了。因此MAXQ方法需要根据学习到的策略来依次调用不同的子任务。本文所描述的自动分层方法，在任务的层次结构建立后，将会使用MAXQ方法学习任务图得到最优策略。

1.3 MAXQ值函数分解

MAXQ方法的核心是MAXQ值函数分解，经过对值函数的分解，使得可以通过对子任务的值函数进行结合就可以得到完整的值函数。由前文的介绍，可以知道Q函数能够表示期望累积回报。而为了在Q值函数中表现出任务的分层结构，需要对原始的Q函数进行拓展。在MAXQ方法中，用Q^π(i, s, a) 表示在进行子任务M_i，环境状态为s时执行了动作a，然后遵循策略π直到M_i终止，所得到的期望累积回报。a可以是一个基本动作，也可以是M_i的一个子任务，则Q函数可以写为如下形式：

$ {Q^\pi }\left( {i, s, a} \right) = {V^\pi }\left( {a, s} \right) + \sum\limits_{s', N} {P_i^\pi \left( {s', N{\rm{|}}s, a} \right){\gamma ^N}{Q^\pi }\left( {i, s', \pi \left( {s'} \right)} \right)} $

(6)

其中：V^π(a, s) 表示在状态s执行动作a所得到的直接奖赏R(a, s)=V^π(a, s)；$\sum\limits_{s',N} {P_i^\pi \left( {s',N|s,a} \right){\gamma ^N}{Q^\pi }(i,s',\pi (s'))} $表示在状态s执行动作a经过N个时间步后状态转变为s′，在状态s′完成子任务M_i的期望折扣回报，在MAXQ方法中，这一项被称为完成函数。

完成函数C^π(i, a, s) 的一般形式如下：

$ {C^\pi }\left( {i, s, a} \right) = \sum\limits_{s', N} {P_i^\pi \left( {s', N{\rm{|}}s, a} \right){\gamma ^N}{Q^\pi }\left( {i, s', \pi \left( {s'} \right)} \right)} $

(7)

表示在状态s时执行动作a后完成子任务M_i所获得的期望折扣回报，其中a既可以是一个原子任务也可以是一个复合任务。该回报值从a开始执行时计算折扣。根据以上定义，Q函数可以写为如下形式：

$ {Q^\pi }\left( {i, s, a} \right) = {V^\pi }\left( {a, s} \right) + {C^\pi }\left( {i, s, a} \right) $

(8)

值函数V^π(a, s) 可以通过式 (9) 计算：

$ {V^\pi }\left( {a, s} \right) = \left\{ \begin{array}{l} {Q^\pi }\left( {a, s, {\pi _a}\left( s \right)} \right), \;\;\;\;\;\;\;\;\;\;a是复合任务\\ \sum\limits_{s'} {P\left( {s'|s, a} \right)R\left( {s'|s, a} \right), a是原子任务} \end{array} \right. $

(9)

根据以上描述可以知道，在策略π下，完整的学习任务M可以被分解为多个子任务M₀, M₁, …, M_n，根任务M₀处的值函数V^π(0, s) 就可以被分解为多个完成函数C^π(i, a, s)，其中i=0, 1，…, n。MAXQ值函数分解的一般形式如下：

$ {V^\pi }\left( {0, s} \right) = {V^\pi }\left( {{a_m}, s} \right) + {C^\pi }\left( {{a_{m-1}}, s, {a_m}} \right) + \cdots + {C^\pi }\left( {{a_1}, s, {a_2}} \right) + {C^\pi }\left( {0, s, {a_1}} \right) $

(10)

其中a₀, a₁, a₂, …, a_m表示在任务图中根据策略π，从根任务到原子任务的子任务调用路径，图 2是值函数分解过程的图形化展示 (r₁, r₂, …, r₁₄表示在时间点1, 2, …, 14执行基本动作获得的回报序列)。

2 基于动作的层次结构划分方法 2.1 动作空间划分的基本思想

在分层强化学习中，很多方法都会对状态空间进行抽象处理，在这些处理方法中，找出瓶颈状态并将其当作子目标是一种典型的方法，在基于Option的自动分层方法中尤为常见。识别子目标的常用标准有访问次数^[17]、访问次数落差变化率^[18]、单向值^[11]等。这些方法在有明显的可划分环境中效果很好，不过在空间较大或者不易划分的环境中瓶颈状态的识别并不理想。难以达到划分学习任务加快学习速度的目的，最终的效果也与单纯使用Qlearning、Sarsa等方法的效果相近。为了在任何环境下都可以自动划分出层次结构，本文提出一种不需考虑外部环境，只通过划分动作空间构造分层结构的方法。

在Agent完成目标的过程中，环境状态可以视为一个向量，每一次动作的执行都会使该向量的某些分量发生改变。通过记录每个动作执行后，有哪些状态变量发生了改变，就可以将完整的动作集划分为多个子集。然后利用这些子集来构造MAXQ方法中的复合型子任务，只要确定了这些子任务之间的层次结构也就得到了完整的任务图。在确定复合型子任务之间的上下层关系时，遵循的一个基本规则是：在完成目标过程中，执行次数多的子任务应该在下层，执行次数少的子任务应该在上层。此外，为了构造更复杂的子任务，需要引入瓶颈动作的概念。在完成目标的过程中，如果某个时刻不执行某个动作，整个任务就无法进行下去或者无法进入下一个阶段，那么这个动作就是瓶颈动作。根据瓶颈动作的特征，如果在某个状态下只有一个可以执行的动作, 那就可以认定该动作是一个瓶颈动作。在完成目标的过程中如果记录每一次动作的执行，就会发现动作执行的轨迹中含有多个瓶颈动作，在相邻的瓶颈动作之间可能会存在多个普通动作。

下文中使用b₁, b₂, …, b_i表示瓶颈动作，a_{i, j}表示在动作轨迹中瓶颈动作b_i-1后执行的第j个动作。动作执行轨迹的一般形式如下：

a_{0, 1}, a_{0, 2}, …, a_{0, j}, b₁, a_{1, 1}, a_{1, 2}, …, a_{1, j}, b₂, …, a_{i-1, 1}, a_{i-1, 2}, …, a_{i-1, j}, b_i

将动作轨迹中的瓶颈动作b_i视为子任务M_i完成的标志，那么在前一个瓶颈动作b_i-1与b_i之间的动作a_{i, j}就可以当作为了完成M_i而必须先完成的下层子任务。在构造分层结构时，记录下瓶颈动作之间的动作执行轨迹 (即动作a)，以及动作a的执行次数f_a。由于基本动作都已经被分组并构造为多个复合子任务，那么就可以找到每一个基本动作a在当前所属的子任务M_a，以及瓶颈动作b当前所属的子任务M_b。对子任务M_i，假设M_i有n个孩子任务，分别记为m₁, m₂, …, m_n，则子任务M_i的访问次数F_Mi由式 (11) 计算：

$ \begin{array}{l} {F_{{M_i}}} = \\ \left\{ \begin{array}{l} {f_{{m_1}}} + {f_{{m_2}}}{\rm{ + }} \cdots {\rm{ + }}{f_{{m_n}}}, {m_1}, {m_2}, \ldots, {m_{\rm{n}}}全都是复合任务\\ {f_{{m_{p1}}}} + {f_{{m_{p2}}}}{\rm{ + }} \cdots {\rm{ + }}{f_{{m_{pk}}}}, {m_1}, {m_2}, \ldots, {m_n}中存在原子任务{m_{p1}}, {m_{p2}}, ..., {m_{pk}} \end{array} \right. \end{array} $

(11)

根据执行次数与上下关系的基本规则，可以认为访问次数比M_b高的M_a在任务图中位于M_b的上层，反之则位于M_b的下层。由这种上下层关系，就可以将M_a与M_b合并为一个新的复合子任务。为了减少调序操作，在构造新的复合子任务时，优先将M_b和位于M_b下层的M_a合并。当所有复合子任务都合并在一起时，完整的任务图就完成了。

2.2 自动分层算法描述

为了便于描述，在后文中会将子任务间的隶属关系，描述为父任务与孩子任务，一个复合任务中最上层的子任务称为根任务。下面给出自动分层算法的描述。

输入 动作集A，其中包含Agent可以执行的所有基本动作。

输出 根任务M₀，M₀及其下属的所有子任务构成了完整的任务层次结构。

1) 执行一个随机的策略π_random，Agent从起点出发直到完成任务目标。记录在整个过程中每个基本动作执行的次数，记为f_a，a∈A。根据各动作所影响的状态变量，将A划分为多个子集A₁, A₂, …, A_n。

2) 对于每一个动作子集A_i，如果|A_i|＞1，构造一个复合任务M_i，A_i中的每个元素都是M_i下属的原子任务；如果|A_i|＝1，则只构造一个单独的原子任务。M₁, M₂, …, M_n组成一个新的集合TaskSet，TaskSet中包含当前所有的子任务。

3) Agent从起点出发，依据π_random执行一个随机动作。

4) 设置一个空列表trail，记录基本动作执行的轨迹；设置两个空的集合uppertask、lowertask记录上下层子任务。

5) 如果当前状态是终止状态则转到第11) 步，否则将当前可以执行的基本动作组成一个集合U。

6) 如果|U|＞1，则执行一个随机动作a(a∈U)，将a添加到trail尾部，转到第5) 步。

7) 如果|U|＝1，则U中的动作就是当前的瓶颈动作b，M_b表示b所属的根任务。对trail中的每个动作a，同样找到它们各自的根任务M_a，M_a、M_b∈TaskSet。比较M_b与M_a的访问次数F_Mb, F_Ma：如果F_Mb＜F_Ma，lowertask=lowertask∪M_a；如果F_Mb＞F_Ma，uppertask=uppertask∪M_a。

8) 如果|lowertask|≠0，新建一个复合任务M_lower，并使lowertask中的元素全部成为M_lower的子任务。

① 如果M_b为原子任务，表示b所属的动作子集A_b中只有一个元素。新建一个复合任务M_new，令M_b和M_lower为M_new的子任务。TaskSet=(TaskSet-M_b-lowertask)∪M_new。

② 如果M_b为复合任务，表示b此时已经加入某个复合任务中。找到b的父任务M_bp，设置集合children表示M_bp当前的子任务集合，并且设置一个空的集合newchildren。对于children中的每个子任务M_i：如果M_i为原子任务，以M_i和M_lower为子任务构造一个新的复合任务M_new，newchildren=newchildren∪M_new；如果M_i为复合任务，令M_i成为M_lower的一个子任务。

最终，如果|newchildren|＝1，即children中只有一个原子任务 (也就是b)，其余都是复合任务。则将该元素的子任务集合作为M_bp的子任务集合；如果|newchildren|＞1，即children中有多个原子任务，则将newchildren作为M_bp的子任务集合。

9) 如果|lowertask|＝0，并且|uppertask|≠0，说明此时M_b应为uppertask中元素的下层子任务。对于集合uppertask中的每个子任务M_upper，使用一种深度优先的方法在M_upper的下属子任务中找到访问次数比M_b多的子任务，记为M_re。TaskSet=(TaskSet-M_b)∪M_re，将M_re放回TaskSet，其在M_upper的任务结构中的位置被替换为M_b。

10) 执行瓶颈动作b，转到第4) 步。

11) 结束，此时|TaskSet|＝1，子任务的层次结构构造完成。

2.3 子任务的终止条件

在MAXQ算法及一些基于MAXQ的改进算法中，在对已知的分层结构进行学习时，判断子任务是否终止，通常的方法是判断当前状态是否为相应子任务的终止状态 (也称为离开状态)。不过由于在上述自动分层算法构造分层结构的过程中，很难记录子任务的每个终止状态，所以需要一种新的判断子任务是否终止的方法。本文提出一种通过比较当前状态的可用动作和当前子任务包含的基本动作，判断是否终止当前子任务的方法。假设当前执行的子任务为M，所处的状态为s，下面给出判断M是否终止的方法流程描述：

1) 用集合Actset表示当前状态s处的所有可用基本动作。

2) 用集合Act表示子任务M下属的所有基本动作。

3) 如果M的子任务中有复合任务，并且Actset中存在Act中的元素，则此时M还不能终止。

4) 如果M的子任务中有复合任务，但是Actset中没有Act中的元素，则M终止。

5) 如果M的子任务中只有原子任务，并且正是由于执行了其中的某个原子任务而到达了状态s，则M终止; 否则M继续。

3 实验与分析 3.1 实验设置

为了验证本文算法自动分层的有效性，以及该层次结构适用于MAXQ方法并能提升寻找最优策略的效率，本文的实验使用强化学习研究中常见的出租车问题作为任务背景。Agent所处的环境如图 3所示，在一个10×10网格环境中，在4个角有4个站台A、B、C、D，出租车会出现在整个环境中的一个随机位置，乘客会随机出现在四个站台中的一个，乘客会在另外三个站台中随机选择一个作为目的地。出租车的任务就是从起点出发，接乘客上车，将乘客送到目的地下车。

实验中出租车可以执行7个基本动作，分别是东、西、南、北、加燃料、接乘客和放下乘客。在实验中，执行东、西、南、北4个动作会使出租车向相应方向移动一格，并获得-1的回报，如果因为受到墙壁或燃料限制而无法移动则获得-10的回报。在移动5次后，燃料会用尽，此时必须执行加燃料动作，否则就无法移动，执行加燃料动作后获得-1的回报。在乘客所在位置必须执行接乘客动作，在目的地则必须要执行放下乘客的动作，成功接到乘客或放下乘客后会获得20的回报，如果没有在正确位置执行“接乘客”与“放乘客”动作会得到-10的回报。为了对比自动分层后的学习效率，分别使用QLearning、Sarsa和已经得到层次结构的MAXQ方法三种强化学习方法寻找出租车问题的最优策略。在学习过程中统一设定学习因子α=0.2，折扣因子γ=0.9，探索策略ε=0.8。每次实验运行100个episode，每个episode代表出租车从起点出发，然后接到乘客，最后在目的地放下乘客的完整过程。为了增加环境的复杂性，设定在每个episode开始时，有30%的概率重新选择出租车的起点、乘客所在的站台和目的地。

3.2 实验结果与分析

在上述环境中，经过自动分层算法得到如图 4(b)所示层次结构，可以看出该层次结构符合出租车问题的一般过程。除了上文所述无障碍物环境，在图 4(a)所示环境中也可以构造同样的层次结构，这说明使用本文算法，环境的变化不会影响层次结构的构造。

表 1展示了在两种实验环境中进行20次构造层次结构的实验所得到的结果。可以看出，在添加障碍后，所需的动作执行次数增加了。这是因为在本文的算法中，需要先使用随机策略运行一个完整的episode，通过这个episode的动作执行轨迹以及其中每种动作的执行次数才可以得到层次结构。由于加入障碍后，随机执行动作去完成一个episode所需的步数提高了，因此使得构造层次结构的时间相应地加长了。

下面展示使用三种算法得到的学习结果，其中图 5为平均步数的变化，图 6为平均回报的变化。

在平均步数的变化趋势中可以看出，经过自动分层的MAXQ方法在整个实验过程中变化趋势较为平稳。在学习前期的episode中就可以通过比较少的动作执行数完成任务，同一时期QLearning和Sarsa方法都需要执行更多的动作。在运行20次episode后，三种算法都趋于平稳，最终的平均执行次数比较相近。之所以会有这样的结果，主要是因为使用MAXQ方法时，学习任务被分为多个子任务，在完成子任务的过程中可以忽略那些和完成该子任务无关的动作。比如，在“导航”子任务中就可以直接忽略“接乘客”和“放乘客”这两个动作，在“移动”子任务又可以忽略“加燃料”动作。由于在每一阶段的子任务中所考虑的动作数减少了，所以从一开始MAXQ方法就可以通过更少的执行次数完成目标。而QLearning和Sarsa在前期使用接近随机策略的方法探索实验环境，在积累了多个episode的经验后，才逐渐收敛到最优策略。通过平均回报的变化趋势，可以看出MAXQ方法的平均回报明显优于其他两种方法。这也是由于层次结构的存在使得在学习过程中执行动作的随机性下降了，执行错误动作得到-10惩罚的次数减少很多。

图 7展示了在相同实验环境下完成100次episode平均时间的变化趋势。可以发现MAXQ与Sarsa方法所用时间明显少于QLearning，即使在任务后期episode的平均步数相近时，QLearning中episode所用的平均时间仍明显多于MAXQ与Sarsa。

4 结语

本文在现有的分层强化学习的基础上，提出了一种基于动作空间划分的自动分层MAXQ方法。利用在随机探索过程中，动作执行时所影响的状态分量划分动作集。根据动作执行的次序，推导出动作子集之间的层次关系。此外，对MAXQ方法中判断子任务终止的条件进行了修改，使通过动作空间得到的层次结构适用于MAXQ学习算法。通过出租车问题的实验，验证了分层的有效性，也证明了该方法得到的层次结构可以通过MAXQ方法找到最优策略。

本文所提方法仍然存在一些需要完善之处，比如在学习过程中，每次执行的步数相近，虽然稳定但却没有收敛的趋势。在环境会随时发生变化的情况下效果很好，但在固定不变的环境中，例如在出租车问题中固定每次乘客出现的位置和目的地位置时，得到的结果并不理想。下一步的研究目标是进一步优化学习算法，使之适用于更广泛的环境。