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

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

Problem Statement
The Boolean Task Algebra (BTA) offers a framework for zero-shot task composition in Reinforcement Learning (RL) by equipping goal-reaching tasks with Boolean operations (conjunction, disjunction, negation). The original formulation posits that to guarantee optimal representational completeness for a set of goals $G$, an agent must learn a collection of base tasks of size $O(\lceil \log_2 |G| \rceil)$ in addition to universal and empty tasks. These base tasks are then combined via element-wise operations on extended Q-value functions to derive policies for complex composite tasks. However, this approach incurs significant training costs due to the number of base tasks required and computational costs during composition due to the complexity of combining value functions.

Methodology and Theoretical Analysis
This paper revisits the structural assumptions of the BTA, specifically within deterministic Markov Decision Processes (MDPs) with absorbing goal states. The authors formalize a "collapse" in the space of optimal extended Q-value functions.

1. Representational Collapse: The authors prove that in deterministic MDPs, every optimal extended Q-value function is fully determined by only two components: the extended Q-function of the universal task ($M_U$, which assigns the highest terminal reward to every goal) and the empty task ($M_\emptyset$, which assigns the lowest terminal reward to every goal).

   • Proposition 1 & Lemma 1: For any task $M$, the optimal extended Q-value function $\bar{Q}^*_M(s, g, a)$ for a specific goal $g$ is identical to the slice of the universal task if $g$ is a desired goal for $M$, and identical to the slice of the empty task if $g$ is not a desired goal.
   • Implication: Learning the logarithmic set of base tasks proposed in the original BTA is redundant, as it duplicates information already contained in the universal and empty tasks.

2. Goal-Set Based Composition: Based on this collapse, the paper proposes a new composition method. Instead of learning a Boolean basis of tasks, the agent learns only the universal and empty tasks. Composition is performed by:

   • Identifying the set of desired goals $G^+_M$ for a new composite task.
   • Constructing the new extended Q-value function by selecting the appropriate "slices" from the pre-learned universal and empty Q-functions.
   • Theorem 1: Establishes an isomorphism between the task algebra and the power set of goals, allowing logical operations to be performed directly on goal sets rather than through element-wise manipulation of value functions.

3. Stochastic MDPs: The paper investigates whether this simplification holds for stochastic MDPs. Proposition 2 provides a counterexample demonstrating that in stochastic settings, the independence between goals disappears. In the worst case, a different optimal policy is required for each of the $2^{|G|} - 1$ possible non-empty subsets of goals. Consequently, optimal composition in stochastic environments may require accounting for an exponential number of policies, and the deterministic collapse does not hold.

Key Contributions

1. Formalization of Representational Limitation: The authors formalize the collapse of the BTA representation space, proving that learning base tasks beyond the universal and empty tasks is unnecessary for deterministic MDPs. This reduces the training cost from $O(\lceil \log_2 |G| \rceil)$ to a constant (learning only two tasks).
2. Efficient Composition Method: A new method is proposed that replaces complex value function operations with simple array lookups and slice selections. This reduces the computational cost of composition from $O(\lceil \log_2 |G| \rceil \times |G| \times |S| \times |A|)$ to $O(|G| \times |S| \times |A|)$.
3. Identification of Stochastic Limitations: The paper identifies a fundamental limitation of BTA-style composition in stochastic MDPs, showing that the independence of goal slices breaks down, potentially requiring exponential resources for optimal composition.

Experimental Results
The authors evaluate their method across tabular, visual, function-approximation, and continuous-control domains (Rooms, Boxman, Office Gridworld, and Safety Gym).

• Performance: Experiments confirm that learning additional base tasks does not yield better performance upon convergence. The goal-set method (using only universal and empty tasks) achieves the same optimal policy as the original base-task method.
• Convergence Speed: In the Rooms environment, the goal-set method converges to the optimal policy faster than the base-task method when measured by total training budget, as it avoids the mixing of value functions via max/min operations which can be detrimental before convergence.
• Composition Time: The goal-set method consistently achieves significantly lower composition times compared to the base-task approach. The performance gap widens as the number of goals increases.
• Skill Machines: When applied to the Skill Machines framework (which handles Linear Temporal Logic specifications), the proposed method retains the training efficiency of the existing framework while further reducing the composition time.

Significance and Claims
The paper claims that the Boolean Task Algebra framework can be simplified without sacrificing optimality in deterministic settings. By recognizing that the space of optimal extended Q-value functions collapses to two fundamental functions, the authors demonstrate that the original requirement for a logarithmic number of base tasks is redundant. This leads to a more direct formulation of task composition that reduces both learning costs and composition time. The work provides a theoretical foundation for why simpler composition strategies work and highlights the specific conditions (determinism) under which this efficiency is guaranteed, while cautioning that these guarantees do not extend to stochastic environments where optimal composition may become exponentially complex.