A Goal-Set Characterization of Task Composition in the Boolean Task Algebra

技术摘要：布尔任务代数中基于目标集任务组合的特征化研究

问题陈述
布尔任务代数（Boolean Task Algebra, BTA）为强化学习（RL）中的零样本任务组合提供了一个框架，通过为目标达成任务配备布尔运算（与、或、非）。原始表述认为，为了保证对一组目标 $G$ 的最优表示完备性，智能体除了通用任务和空任务外，还必须学习规模为 $O(\lceil \log_2 |G| \rceil)$ 的基任务集合。这些基任务随后通过在扩展 Q 函数上进行逐元素运算来组合，从而推导出复杂复合任务的策略。然而，这种方法由于所需基任务的数量较多而导致显著的训练成本，且由于组合价值函数的复杂性而导致计算成本较高。

方法论与理论分析
本文重新审视了 BTA 的结构假设，特别是在具有吸收目标状态的确定性马尔可夫决策过程（MDPs）中。作者形式化了最优扩展 Q 函数空间中的一种“坍缩”现象。

1. 表示坍缩（Representational Collapse）： 作者证明，在确定性 MDP 中，每一个最优扩展 Q 函数都完全由两个组件决定：通用任务（$M_U$，它为每个目标分配最高终端奖励）的扩展 Q 函数，以及空任务（$M_\emptyset$，它为每个目标分配最低终端奖励）的扩展 Q 函数。

   • 命题 1 与引理 1： 对于任何任务 $M$，对于特定目标 $g$，其最优扩展 Q 函数 $\bar{Q}^*_M(s, g, a)$ 等同于通用任务在该目标处的切片（slice），如果 $g$ 是 $M$ 的期望目标；若 $g$ 不是期望目标，则等同于空任务在该目标处的切片。
   • 启示： 学习原始 BTA 中所建议的对数级基任务集合是冗余的，因为这些任务所包含的信息已包含在通用任务和空任务之中。

2. 基于目标集的组合： 基于这种坍缩现象，本文提出了一种新的组合方法。智能体不再学习布尔基任务，而是仅学习通用任务和空任务。组合过程通过以下方式进行：

   • 识别新复合任务的期望目标集 $G^+_M$。
   • 通过从预先学习的通用和空 Q 函数中选择相应的“切片”，构建新的扩展 Q 函数。
   • 定理 1： 建立了任务代数与目标幂集之间的同构关系，允许直接在目标集上执行逻辑运算，而非通过对价值函数进行逐元素操作。

3. 随机 MDPs： 本文研究了这种简化在随机 MDPs 中是否成立。命题 2 提供了一个反例，证明在随机设置中，目标之间的独立性消失了。在最坏情况下，对于 $2^{|G|} - 1$ 个可能的非空子集，都需要不同的最优策略。因此，在随机环境中进行最优组合可能需要考虑指数数量的策略，且确定性坍缩并不成立。

核心贡献

1. 形式化表示限制： 作者形式化了 BTA 表示空间的坍缩，证明在确定性 MDP 中，学习除通用任务和空任务之外的基任务是不必要的。这使得学习成本从 $O(\lceil \log_2 |G| \rceil)$ 降低到了常数级（仅学习两个任务）。
2. 高效的组合方法： 提出了一种新方法，用简单的数组查找和切片选择取代了复杂的价值函数运算。这使组合的计算成本从 $O(\lceil \log_2 |G| \rceil \times |G| \times |S| \times |A|)$ 降低到 $O(|G| \times |S| \times |A|)$。
3. 识别随机性局限： 本文指出了 BTA 式组合在随机 MDPs 中的一个根本局限，即目标切片的独立性会失效，这可能导致最优组合需要指数级的资源。

实验结果
作者在表格型、视觉、函数逼近和连续控制领域（Rooms, Boxman, Office Gridworld, 以及 Safety Gym）对该方法进行了评估。

• 性能： 实验证实，学习额外的基任务并不会在收敛后带来更好的性能。目标集方法（仅使用通用和空任务）能达到与原始基任务方法相同的最优策略。
• 收敛速度： 在 Rooms 环境中，以总训练预算衡量，目标集方法比基任务方法更快收敛到最优策略，因为它避免了在收敛前通过 max/min 操作进行价值函数混合所带来的不利影响。
• 组合时间： 目标集方法在组合时间上始终显著低于基任务方法。随着目标数量的增加，这种性能差距进一步扩大。
• 技能机器（Skill Machines）： 当应用于处理线性时序逻辑（LTL）规范的 Skill Machines 框架时，所提方法在保持现有框架训练效率的同时，进一步降低了组合时间。

意义与主张
本文声称，在确定性设置下，布尔任务代数框架可以在不牺牲最优性的情况下进行简化。通过认识到最优扩展 Q 函数的空间坍缩为两个基本函数，作者证明了原始要求学习对数个基任务的要求是冗余的。这导致了一种更直接的任务组合形式，既降低了学习成本，也缩短了组合时间。这项工作为为什么更简单的组合策略有效提供了理论基础，并强调了实现这种效率的具体条件（确定性），同时提醒读者，这些保证并不能推广到可能变得具有指数级复杂度的随机环境。