摘要

• 针对问题：分层强化学习需要人工给出层次结构这一问题；基于状态空间的自动分层方法在环境状态中没有明显子目标时分层效果并不理想
• 提出方法：基于动作空间的自动构造层次结构方法；对MAXQ的子任务终止条件进行修改；
• 细节：动作集合划分子集 $\to$ 不同状态下识别瓶颈动作 $\to$ 确定动作子集之间的上下层关系 $\to$ 构造层次结构
• 结果：与Q/SARSA相比，可以自动构建层次，具有鲁棒性；

关键词

• 强化学习;
• 分层强化学习;
• 自动分层方法;
• 马尔可夫决策过程;
• 子任务;

0 引言

减小“维数灾难”的影响 $\to$ 将分层、抽象等机制引入强化学习 $\to$ 本质是：既对状态空间进行降维、又实现任务分层 $\to$ 较小的低维空间中逐步解决子任务

主流：MAXQ、Option和HAM
HAM $\to$ Hierarchies of Abstract Machine 分层抽象机
共同点 $\to$ 需要先验知识

本文工作：

1. 提出一种自动分层算法；
2. 提出了一种新的判断子任务是否结束的方法；

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

1.1 马尔可夫决策过程

分层强化学习会对原始问题进行抽象
$\to$ 可执行的动作会被替换为需要多个时间步完成的宏动作
$\to$ 引入"半马尔可夫决策过程"SMDP

SMDP可以分为离散SMDP和连续SMDP
离散SMDP的时间间隔是单步间隔的整数倍
值函数与Q函数在单步间隔的基础上增加额外的单步间隔奖励就行

1.2 分层强化学习

1. 分层强化学习的抽象方法分类：

2. 典型的强化学习方法分类：

1.3 MAXQ 值函数分解

MAXQ的核心 $\to$ MAXQ的值函数分解

$a$既可能是原子型动作，也可能是组合型动作

引入完成函数后可以对Q函数分解成当前的即时奖励和一系列的完成函数

2 基于动作的层次结构划分方法

2.1 动作空间划分的基本思想

识别子目标的常用标准：
访问次数、访问次数落差变化率、单向值
优点 $\to$ 在简单有限的环境中效果较好
缺点 $\to$ 连续环境、高维环境表现不好

本文提出一种不需考虑外部环境，只通过划分动作空间构造分层结构的方法。
思路：状态 $\to$ 抽象成一维的向量 $\to$ 记录动作的一维向量分量的影响；
原则：执行次数多的子任务 $\to$ 下层；执行次数高 $\to$ 上层；
引入瓶颈动作：不执行该动作无法进入下一个子任务 。
$\to$ 特殊地：某个状态下只有一个动作，这个就是瓶颈动作。
$\to$ 意义：判断子任务是否完成/结束的标志；两个瓶颈动作之间的普通动作走行的状态应该划分成一个子任务。
$\to$ 在构造分层结构时，记录下瓶颈动作之间的动作执行轨迹(即动作$a$) ，以及动作$a$的执行次数$f_a$。

子任务$M_i$的访问频率计算式：

可以认为访问次数比 $M_b$ 高的 $M_a$ 在任务图中位于 $M_b$ 的上层，反之则位于 $M_b$的下层。

2.2 自动分层算法描述

2.3 子任务的终止条件

本文提出一种通过比较当前状态的可用动作和当前子任务包含的基本动作
判断是否终止当前子任务的方法

3 实验与分析

3.1 实验设置

基本动作：东、西、南、北、加燃料、接乘客和放下乘客
奖励函数设置：

1. 因为受到墙壁或燃料限制而无法移动，-10
2. 执行加燃料动作，-1
3. 成功接到乘客或放下乘客，20
4. 没有在正确位置执行，-10

为了增加环境的复杂性 $\to$ 有 30% 的概率重新选择出租车的起点、乘客所在的站台和目的地

3.2 实验结果与分析

实验结论：

1. 经过自动分层的 MAXQ 方法在整个实验过程中变化趋势较为平稳
2. 前期：比较少的动作执行数完成任务
3. 理由：在完成子任务的过程中可以忽略那些和完成该子任务无关的动作
4. 平均回报的变化趋势：MAXQ较好
5. MAXQ用的时间最少，比Q和SARSA

4 结语