布尔任务代数中任务组合的目标集刻画

# 布尔任务代数中任务组合的目标集刻画

来源：https://arxiv.org/html/2606.04053
Eduardo Terrés\-Caballero¹ Herke van Hoof² ¹阿姆斯特丹大学信息学研究所 ²阿姆斯特丹大学 AMLab

###### 摘要

布尔任务代数（BTA）通过为目标到达任务赋予布尔运算，为强化学习中的零样本任务组合提供了一个有原则的框架。我们重新审视其结构假设，并形式化了最优扩展 Q 值函数空间中的一种坍缩现象：在确定性 MDP 中，每个此类函数完全由全集任务和空集任务所决定。这使得原始 BTA 框架中提出的对数规模基础任务集变得冗余。基于这一观察，我们引入了一种基于目标集的组合方法，该方法对目标集执行逻辑运算，并通过从全集和空集值函数中选取切片来重建组合值函数。这降低了标准 BTA 的学习成本，同时缩短了 BTA 和 Skill Machines 的组合时间，同时保持了策略性能。在表格、视觉、函数近似和连续控制领域的实验表明，学习额外的基础任务并不会带来更好的性能。最后，我们研究了随机场景，并提供了一个反例，说明这种坍缩不一定成立——即最优组合可能需要考虑目标数量指数级数量的策略。代码可在 https://github.com/EduardoTerres/bta_paper 获取。

## 1 引言

组合性是开发能够在共享环境中推理并解决多个任务的智能体的核心原则。当任务具有结构性时，可以将复杂目标表达为更简单目标的组合，从而实现对已习得行为的复用。在这一方向上，Nangue Tasse 等人\[2020 (https://arxiv.org/html/2606.04053#bib.bib1)\]引入了布尔任务代数（BTA），并证明在特定假设下，任务空间具有布尔代数的结构。通过对奖励函数及其关联扩展值函数进行操作，BTA 实现了任务的精确逻辑组合，并为零样本推导组合任务的最优策略提供了有原则的框架。这一代数结构进一步建立了任务代数与最优扩展 Q 值函数代数之间的同态，使得组合可以直接在扩展值函数空间中表达。该代数需要学习一组基础任务，其组合覆盖整个代数空间。原始公式提出学习 $\mathcal{O}(\lceil\log|\mathcal{G}|\rceil)$ 个此类任务，以保证最优的表示完备性。

遵循 Tasse 等人\[2022 (https://arxiv.org/html/2606.04053#bib.bib35)\]的洞察，我们形式化了 BTA 中发生这种坍缩的原因，以及基于此框架构建的方法（例如 Nangue Tasse 等人\[2024 (https://arxiv.org/html/2606.04053#bib.bib33)\]）在组合计算时间上可以做出哪些简化。我们证明，每个最优扩展 Q 函数都可以仅由两个分量构造：全集任务的扩展 Q 函数（为每个目标分配最高终端奖励）和空集任务的扩展 Q 函数（为每个目标分配最低终端奖励）。

这一观察引出了 BTA 更直接的表述形式。由于一个任务由产生较高奖励的目标集所决定，组合可以通过关注所需的目标集来实现。只要这两个函数覆盖整个目标空间，组合任务的扩展 Q 值函数便可以通过从仅两个已学习扩展 Q 值函数中选取适当切片来重建。这消除了学习布尔基础任务集的需求，带来了一系列计算上的优势。此外，我们研究了这种组合时间优化在随机 MDP 场景中的适用性。在确定性情形下，以最优方式进行组合涉及独立学习目标切片，然后对所需目标集执行布尔运算，其规模与所需目标集的大小呈线性关系。对于随机 MDP，我们提供了一个反例，说明在最坏情况下，每个所需目标集（原始目标集的子集）可能具有不同的最优策略。因此，目标之间的独立性消失，使得组合过程中需要考虑的最优策略数量随目标幂集的大小增长。

##### 贡献。

本工作的主要贡献如下：

1. 1\.我们形式化了 Tasse 等人\[2022 (https://arxiv.org/html/2606.04053#bib.bib35)\]所述的 BTA 框架中的表示局限性，将训练成本从 $\mathcal{O}(\lceil\log_2|G|\rceil)$ 降至常数。我们通过实验表明，这一改进在表格和函数近似设置中均不影响收敛性，并且训练额外的基础任务并不会在收敛后带来更好的性能。
2. 2\.我们提出了一种新的任务组合方法，该方法仅需数组查找，无需对已学习值函数执行操作。我们在表格、函数近似、视觉和连续控制环境中实验验证了其计算收益。
3. 3\.我们发现了基于确定性 BTA 风格的组合方法在随机 MDP 中的局限性。虽然确定性任务可以通过独立组合目标切片来实现，但在随机转移条件下这种独立性消失，需要处理相对于目标集大小呈指数级数量的最优策略。

## 2 相关工作

##### 强化学习中的零样本组合学习。

控制理论中关于组合的早期工作 Todorov\[2006 (https://arxiv.org/html/2606.04053#bib.bib8), 2009 (https://arxiv.org/html/2606.04053#bib.bib6)\] 证明了线性可解 MDP 通过线性化 Bellman 方程可实现值函数和策略的分解。在此基础上，Barreto 等人\[2017 (https://arxiv.org/html/2606.04053#bib.bib20)\]通过推广继承者表示 Dayan\[1993 (https://arxiv.org/html/2606.04053#bib.bib22)\]引入了继承者特征（SFs）。该框架通过将值函数分解为环境动态（继承者特征）与任务偏好（奖励向量）的点积来实现零样本组合性，使智能体仅需线性组合先前学到的预测映射即可解决新任务。

Schaul 等人\[2015 (https://arxiv.org/html/2606.04053#bib.bib10)\]引入了通用值函数近似器（UVFA），通过在目标表示上条件化值函数来实现对连续目标空间的泛化。Borsa 等人\[2019 (https://arxiv.org/html/2606.04053#bib.bib21)\]随后通过通用继承者特征（USFs）将其与 SF 统一起来，并通过采用 UVFA 架构来近似继承者特征本身，将动态-奖励分解扩展至连续目标空间，克服了标准 SFs 固有的离散任务集局限。Nangue Tasse 等人\[2020 (https://arxiv.org/html/2606.04053#bib.bib1)\]在这些思想基础上引入了*扩展* Q 值函数，在状态和动作维度之外增加了目标维度。这种额外的条件化层次最终允许学习最优策略。

前述方法侧重于组合奖励，另一流派则关注时间与逻辑的组合。这主要通过层次化强化学习（HRL）来处理，它通过将动作分组为可复用的行为来简化长时程任务。基础工作如 Options 框架 Sutton 等人\[1999 (https://arxiv.org/html/2606.04053#bib.bib28)\]将这些行为序列视为单步操作，Andreas 等人\[2017 (https://arxiv.org/html/2606.04053#bib.bib15)\]将其扩展为使用符号草图链接子策略，Vezhnevets 等人\[2017 (https://arxiv.org/html/2606.04053#bib.bib14)\]将其扩展为分离高层规划与低层执行。最后，组合还延伸至形式化规范，其中的方法以结构化逻辑替代固定任务标识符以实现泛化。通过直接将线性时序逻辑 Vaezipoor 等人\[2021 (https://arxiv.org/html/2606.04053#bib.bib12)，Kuric 等人，2024 (https://arxiv.org/html/2606.04053#bib.bib37)\]或自然语言 Hermann 等人\[2017 (https://arxiv.org/html/2606.04053#bib.bib13)\]落地，这些方法使智能体能够仅通过解析命令的逻辑结构来零样本地解释和执行新的复杂约束。

##### 布尔任务代数的前身及后续工作。

布尔任务代数建立在多项工作之上，这些工作确立了如何操纵值函数来表示逻辑运算。Van Niekerk 等人\[2019 (https://arxiv.org/html/2606.04053#bib.bib3)\]证明了虽然标准 RL 可以界定值的组合，但 Soft Q-learning 支持精确的析取（$\lor$）组合，如 Haarnoja 等人\[2017 (https://arxiv.org/html/2606.04053#bib.bib31)\]所示。Haarnoja 等人\[2018 (https://arxiv.org/html/2606.04053#bib.bib2)\]的并行工作表明，任务间的逻辑合取（$\land$）可以通过对 soft 值函数取平均来近似。这些组合机制被 Hunt 等人\[2019 (https://arxiv.org/html/2606.04053#bib.bib16)\]进一步严格分析，他们指出了基于 soft Q 的组合中的理论局限，并提出了修正方案以确保可靠性。

布尔任务代数 Nangue Tasse 等人\[2020 (https://arxiv.org/html/2606.04053#bib.bib1)\]将这些二元概念形式化为一个统一框架，利用编码所有目标到达行为的扩展 Q 值函数来支持任意布尔组合：析取（$\lor$）、合取（$\land$）和否定（$\neg$）。Tasse 等人\[2022 (https://arxiv.org/html/2606.04053#bib.bib35)\]后来指出了最优值函数的特定结构，但未进一步分析由此产生的组合过程简化方案。作者证明，已学习技能的布尔组合能够实现高效的终身迁移和任务空间泛化，但在随机环境中它提供的是有界次优保证而非精确的组合最优性。Nangue Tasse 等人\[2024 (https://arxiv.org/html/2606.04053#bib.bib33)\]将这些简化融入 Skill Machines 框架，该框架通过使用奖励机制引导 Icarte 等人\[2022 (https://arxiv.org/html/2606.04053#bib.bib7)\]的"Skill Machines"，将 BTA 从纯逻辑任务组合扩展至时序逻辑规范，以零样本方式对布尔组合技能进行排序以解决复杂的长时程任务。

## 3 布尔任务代数框架

##### 任务定义与假设。

遵循 Nangue Tasse 等人\[2020 (https://arxiv.org/html/2606.04053#bib.bib1)\]，我们将任务建模为马尔可夫决策过程（MDP），$M=(\mathcal{S},\mathcal{A},\rho,r)$，其中 $\mathcal{S}$ 为状态空间，$\mathcal{A}$ 为动作空间，$\rho(s,a)$ 为转移核，$r(s,a)$ 为奖励函数。我们仅考虑具有确定性转移动态的无折扣 MDP，以及一个吸收集 $\mathcal{G}\subseteq\mathcal{S}$，其元素构成任意给定任务的目标状态。我们定义 $\rho,\mathcal{S}$ 和 $\mathcal{A}$ 并假设它们对所有任务固定不变。我们感兴趣的任务集定义为

$$\mathcal{M}=\big\{(\mathcal{S},\mathcal{A},\rho,r)\;\big|\;r:\mathcal{S}\times\mathcal{A}\to\mathbb{R}\text{ 使得 }r(s,a)=r_{s,a}\;\forall s\notin\mathcal{G},a\in\mathcal{A}\tag{1}$$
$$\text{且}\ r(g,a)\in\{r_{\varnothing},r_{\mathcal{U}}\}\;\forall g\in\mathcal{G},a\in\mathcal{A}\big\}.$$

其中 $r_{s,a}$ 为固定（与任务无关）的非终端奖励，$r_{\varnothing}\leq r_{\mathcal{U}}$ 表示仅有的两种可能终端奖励，从而引出该公式的布尔性质。

##### 扩展 Q 值函数。

标准值函数不足以在布尔框架下组合任务，因为它们仅表示相对于最近目标的期望回报 Nangue Tasse 等人\[2020 (https://arxiv.org/html/2606.04053#bib.bib1)\]。为了能够对所有可能目标进行推理，扩展奖励函数 $\bar{r}:\mathcal{S}\times\mathcal{G}\times\mathcal{A}\to\mathbb{R}$ 定义为：若 $s\notin\mathcal{G}\lor s=g$，则 $\bar{r}(s,g,a)=r(s,a)$；若 $s\in\mathcal{G}\setminus\{g\}$，则 $\bar{r}(s,g,a)=\bar{r}_{\min}$。这里 $\bar{r}_{\min}$ 是一个较大的负惩罚，确保到达非期望目标将产生最差可能的回报。相应的扩展 Q 值函数为

$$\bar{Q}^{\pi}(s,g,a)=\bar{r}(s,g,a)+\int_{\mathcal{S}}\bar{V}^{\pi}(s^{\prime},g)\,\rho_{(s,a)}(ds^{\prime}),$$

其中 $\bar{V}^{\pi}(s,g)=\mathbb{E}_{\pi}\!\left[\sum_{t=0}^{\infty}\bar{r}(s_t,g,a_t)\right]$，最优对应为 $\bar{Q}^*=\max_{\pi}\bar{Q}^{\pi}$。直观上，$\bar{Q}^*(s,g,a)$ 衡量在状态 $s$ 中执行动作 $a$ 追求目标 $g$ 时的价值，从而编码了如何到达环境中每个目标的信息。任务 $M$ 的标准最优 Q 函数可恢复为 $Q^*_M(s,a)=\max_{g\in\mathcal{G}}\bar{Q}^*_M(s,g,a)$，确立了 $\bar{Q}^*$ 作为更丰富表示的地位，从而实现任务的零样本逻辑组合。

##### 任务与值函数的布尔代数。

我们为任务集 $\mathcal{M}$ 赋予布尔代数结构。我们首先定义两个特殊任务：*全集任务*（始终给予最大奖励），$\mathcal{M}_{\mathcal{U}}=(\mathcal{S},\mathcal{A},\rho,r_{\mathcal{U}}(s,a)=\max_{M\in\mathcal{M}}r_M(s,a))$；以及*空集任务*（始终给予最小奖励），$\mathcal{M}_{\varnothing}=(\mathcal{S},\mathcal{A},\rho,r_{\varnothing}(s,a)=\min_{M\in\mathcal{M}}r_M(s,a))$。它们对应的最优扩展值函数 $\bar{Q}^*_{\mathcal{U}}$ 和 $\bar{Q}^*_{\varnothing}$ 分别表示可达到的最大和最小回报。

对于任意一对任务 $M_1,M_2\in\mathcal{M}$，布尔运算直接定义在其奖励函数上，因为构成 MDP 的其余元素均固定不变。类似地，最优扩展 Q 值函数的组合规则也相应定义：

$(\text{否定}\ \neg)$
$$r_{\lnot M}(s,a)=\big(r_{\mathcal{U}}(s,a)+r_{\varnothing}(s,a)\big)-r_M(s,a),$$
$$\bar{Q}^*_{\lnot M}(s,g,a)=\big(\bar{Q}^*_{\mathcal{U}}(s,g,a)+\bar{Q}^*_{\varnothing}(s,g,a)\big)-\bar{Q}^*_M(s,g,a),$$