Title: Characterizing Task Composition in Boolean Task Algebra via Goal Sets

Abstract

The Boolean Task Algebra (BTA) offers a rigorous framework for zero-shot task composition in reinforcement learning by applying Boolean operations to goal-reaching tasks. This paper re-examines BTA’s structural premises and demonstrates a structural collapse within the space of optimal extended Q-value functions. Specifically, we prove that in deterministic Markov Decision Processes (MDPs), these functions are entirely defined by the universal and empty tasks. Consequently, the logarithmic collection of base tasks suggested in the initial BTA formulation is unnecessary. Leveraging this insight, we propose a new composition strategy based on goal sets, which executes logical operations on these sets and rebuilds composed value functions by extracting specific slices from the universal and empty value functions. This approach lowers the learning overhead associated with standard BTA and accelerates composition times for both BTA and Skill Machines, all without compromising policy performance. Our experiments, spanning tabular, visual, function-approximation, and continuous-control environments, confirm that incorporating extra base tasks fails to improve outcomes. Furthermore, we analyze the stochastic case and present a counterexample demonstrating that the aforementioned collapse does not always apply; in such scenarios, optimal composition may necessitate considering an exponential number of policies relative to the number of goals. The source code is accessible at https://github.com/EduardoTerres/bta_paper.

Source: arXiv Generated at: 2026-06-04 00:00:00 UTC