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

arXiv: https://arxiv.org/abs/2606.04053 · HTML: https://mlsanity.com/paper/2606.04053/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Interpretable and logic-guided RL, one of 15 directions in Deep reinforcement learning methods.
- Builds on 12 of its 25 references that are in the map.
- First posted on arXiv 2 Jun 2026.

## Placed in

- Deep reinforcement learning methods / [Interpretable and logic-guided RL](https://mlsanity.com/deeprl/interpretable-and-logic-guided-rl/)

## Builds on (most cited first, 12 of 12)

- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Successor Features for Transfer in Reinforcement Learning](https://mlsanity.com/paper/1606.05312/) (2016)
- [FeUdal Networks for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1703.01161/) (2017)
- [Modular Multitask Reinforcement Learning with Policy Sketches](https://mlsanity.com/paper/1611.01796/) (2016)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Universal Successor Features Approximators](https://mlsanity.com/paper/1812.07626/) (2018)
- [Grounded Language Learning in a Simulated 3D World](https://mlsanity.com/paper/1706.06551/) (2017)
- [LTL2Action: Generalizing LTL Instructions for Multi-Task RL](https://mlsanity.com/paper/2102.06858/) (2021)
- [Composable Deep Reinforcement Learning for Robotic Manipulation](https://mlsanity.com/paper/1803.06773/) (2018)
- [A Boolean Task Algebra for Reinforcement Learning](https://mlsanity.com/paper/2001.01394/) (2020)
- [Globally Optimal Hierarchical Reinforcement Learning for Linearly-Solvable Markov Decision Processes](https://mlsanity.com/paper/2106.15380/) (2021)
- [Planning with a Learned Policy Basis to Optimally Solve Complex Tasks](https://mlsanity.com/paper/2403.15301/) (2024)

## Abstract (arXiv)

The Boolean Task Algebra (BTA) provides a principled framework for zero-shot task composition in reinforcement learning by equipping goal-reaching tasks with Boolean operations. We revisit its structural assumptions and formalize a collapse in the space of optimal extended Q-value functions: in deterministic MDPs, every such function is fully determined by the universal and empty tasks. This makes the logarithmic set of base tasks proposed in the original BTA formulation redundant. Building on this observation, we introduce a goal-set-based composition method that performs logical operations on goal sets and reconstructs composed value functions by selecting slices from the universal and empty value functions. This reduces learning costs for standard BTA and reduces composition time for both BTA and Skill Machines, while preserving policy performance. Experiments across tabular, visual, function-approximation, and continuous-control domains show that learning additional base tasks does not yield better performance. Finally, we study the stochastic setting and provide a counterexample showing that this collapse need not hold, that is, optimal composition may require accounting for exponentially many policies in the number of goals. Code is available at urlhttps://github.com/EduardoTerres/GoalSetBTA.