[RL] Subgoal Automa

强化学习(Reinforcement Learning)Paper Reading
Induction and Exploitation of Subgoal Automata for Reinforcement Learning

简介#

  • 通过交织进行子目标自动机学习与强化学习
  • 让agent在与环境交互中自动发现任务的子目标结构，并利用该结构加速策略学习
  • 从交互轨迹中归纳子目标自动机，再用自动机指导强化学习，同时用新交互修正自动机

子目标概念机 Subgoal Automata#

子目标自动机是一种有限状态自动机，用于编码任务的子目标结构，其定义为tuple A=< $U,O,\delta_\phi,u_0,u_A,u_R$ >，关键组件包括

  • 状态集合 $U$： 包含初始状态$u_0$、吸收型接受状态 $u_A$（任务成功）、吸收型拒绝状态 $u_R$ （状态失败），以及中间状态（表示子目标完成进度）
  • 观测集 $O$： agent可感知的高层事件，如环境中的咖啡、办公室等实体
  • 逻辑转移函数 $\phi$ ： 核心组件，将状态对映射为基于 $O$ 的命题逻辑公式，使用DNF形式，公式即子目标，如获取咖啡且未到达办公室
  • 转移函数 $\delta_\phi$ ： 基于观测满足的子目标公式，实现自动机状态转移

自动机学习：从轨迹中归纳结构#

核心原理阐述#

自动机通过归纳逻辑编程ILP系统ILPSA从智能体的交互轨迹中学习，核心步骤如下：

  • 轨迹类型：agent与环境交互生成执行轨迹（包含状态、动作、奖励），进一步抽象为观测轨迹（仅保留高层事件序列，与状态空间解耦），分为目标轨迹（任务成功）、死端轨迹（任务失败）、不完整轨迹（未终止）
  • 学习形式化：将自动机学习转化为ILASP任务，以观测轨迹为正例，背景知识为自动机通用行为规则，假设空间为自动机的转移规则
  • 优化机制：
    • 确定性约束：确保同一观测不会出发多个状态转移
    • 对称性破缺：通过BFS遍历排序状态和边，避免等价自动重复搜索，缩小假设空间
    • 最小化保证：通过迭代加深策略，即逐步增加状态数，确保学到的自动机状态数最少

关键概念阐述#

  • 高层事件（观测o）：agent在环境中感知到的关键信息，不是具体的坐标，而是有语义的事件。比如说在OfficeWorld咖啡任务重，环境里有咖啡、办公室、障碍物，这些就是高层事件（O={'coffee','office'}）。agent不管走到哪个坐标，只关心当前位置有没有咖啡和办公室，这就是与状态空间解耦，不用管具体坐标，只看关键事件。
  • 自动机的核心规则：本质是状态+转移条件。
    • 状态：任务进度，如：初始状态——已拿到咖啡——任务成功——任务失败
    • 转移条件：触发状态变化的规则，如：从初始状态->已拿到咖啡的条件是，观测到咖啡

交织机制：自动机学习与强化学习的协同#

ISA并非先学完自动机再学策略，而是动态交织两者，流程如下：

  1. 初始化：自动机仅含初始/接受/拒绝状态，无转移规则；初始化强化学习的Q函数
  2. 交互与轨迹收集：agent执行强化学习策略，生成观测轨迹
  3. 反例检测：若当前自动机无法正确识别轨迹，如任务成功但未进入$u_A$、未终止却进入$u_A/u_R$，则该轨迹为反例
  4. 自动机更新：用反例触发ILASP重新学习自动机，若当前状态数不足则增加状态，重置相关Q函数
  5. 策略优化：用更新后的自动机指导强化学习，将子目标转化为局部任务，加速策略收敛

强化学习适配#

为适配子目标自动机，文章提出两种强化学习算法，均基于选项（Option）框架：

  • 分层强化学习 HRL：为每个自动机边（子目标公式）学习一个选项（局部策略），同时学习元控制器（选择当前状态下的最优选项），选项终止条件为子目标达成或终止，支持跨自动机复用子目标策略
  • 奖励机器Q学习：为每个自动机状态学习一个选项，策略不局限于单个子目标，而是全局优化任务目标。通过奖励塑造（基于状态到$u_A$的距离）加速收敛，保证极限最优
[RL/Basic]MDP Forward