# A Boolean Task Algebra for Reinforcement Learning

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jan 2020.

## Built on by (most cited first, 30 of 48)

- [Open-Ended Learning Leads to Generally Capable Agents](https://mlsanity.com/paper/2107.12808/) (2021)
- [A Survey on Interpretable Reinforcement Learning](https://mlsanity.com/paper/2112.13112/) (2021)
- [On the Expressivity of Markov Reward](https://mlsanity.com/paper/2111.00876/) (2021)
- [MoCoDA: Model-based Counterfactual Data Augmentation](https://mlsanity.com/paper/2210.11287/) (2022)
- [Modular Lifelong Reinforcement Learning via Neural Composition](https://mlsanity.com/paper/2207.00429/) (2022)
- [Discovering Policies with DOMiNO: Diversity Optimization Maintaining Near Optimality](https://mlsanity.com/paper/2205.13521/) (2022)
- [How to Reuse and Compose Knowledge for a Lifetime of Tasks: A Survey on Continual Learning and Functional Composition](https://mlsanity.com/paper/2207.07730/) (2022)
- [Optimistic Linear Support and Successor Features as a Basis for Optimal Policy Transfer](https://mlsanity.com/paper/2206.11326/) (2022)
- [CompoSuite: A Compositional Reinforcement Learning Benchmark](https://mlsanity.com/paper/2207.04136/) (2022)
- [Constraint-Conditioned Policy Optimization for Versatile Safe Reinforcement Learning](https://mlsanity.com/paper/2310.03718/) (2023)
- [A Survey of Continual Reinforcement Learning](https://mlsanity.com/paper/2506.21872/) (2025)
- [Composable Energy Policies for Reactive Motion Generation and Reinforcement Learning](https://mlsanity.com/paper/2105.04962/) (2021)
- [Diversifying AI: Towards Creative Chess with AlphaZero](https://mlsanity.com/paper/2308.09175/) (2023)
- [Constructing a Good Behavior Basis for Transfer using Generalized Policy Updates](https://mlsanity.com/paper/2112.15025/) (2021)
- [Skill Machines: Temporal Logic Skill Composition in Reinforcement Learning](https://mlsanity.com/paper/2205.12532/) (2022)
- [Utilizing Prior Solutions for Reward Shaping and Composition in Entropy-Regularized Reinforcement Learning](https://mlsanity.com/paper/2212.01174/) (2022)
- [Consistent Aggregation of Objectives with Diverse Time Preferences Requires Non-Markovian Rewards](https://mlsanity.com/paper/2310.00435/) (2023)
- [One Subgoal at a Time: Zero-Shot Generalization to Arbitrary Linear Temporal Logic Requirements in Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2508.01561/) (2025)
- [Globally Optimal Hierarchical Reinforcement Learning for Linearly-Solvable Markov Decision Processes](https://mlsanity.com/paper/2106.15380/) (2021)
- [Can Interpretable Reinforcement Learning Manage Prosperity Your Way?](https://mlsanity.com/paper/2202.09064/) (2022)
- [Robotic Manipulation Datasets for Offline Compositional Reinforcement Learning](https://mlsanity.com/paper/2307.07091/) (2023)
- [Lifelong Reinforcement Learning with Temporal Logic Formulas and Reward Machines](https://mlsanity.com/paper/2111.09475/) (2021)
- [Categorical semantics of compositional reinforcement learning](https://mlsanity.com/paper/2208.13687/) (2022)
- [Reinforcement Learning with Knowledge Representation and Reasoning: A Brief Survey](https://mlsanity.com/paper/2304.12090/) (2023)
- [Ground-Compose-Reinforce: Grounding Language in Agentic Behaviours using Limited Data](https://mlsanity.com/paper/2507.10741/) (2025)
- [Hierarchies of Reward Machines](https://mlsanity.com/paper/2205.15752/) (2022)
- [Hierarchically Composing Level Generators for the Creation of Complex Structures](https://mlsanity.com/paper/2302.01561/) (2023)
- [Planning with a Learned Policy Basis to Optimally Solve Complex Tasks](https://mlsanity.com/paper/2403.15301/) (2024)
- [Learning to Follow Language Instructions with Compositional Policies](https://mlsanity.com/paper/2110.04647/) (2021)
- [A Survey on Explainable Reinforcement Learning: Concepts, Algorithms, Challenges](https://mlsanity.com/paper/2211.06665/) (2022)

## Abstract (arXiv)

The ability to compose learned skills to solve new tasks is an important property of lifelong-learning agents. In this work, we formalise the logical composition of tasks as a Boolean algebra. This allows us to formulate new tasks in terms of the negation, disjunction and conjunction of a set of base tasks. We then show that by learning goal-oriented value functions and restricting the transition dynamics of the tasks, an agent can solve these new tasks with no further learning. We prove that by composing these value functions in specific ways, we immediately recover the optimal policies for all tasks expressible under the Boolean algebra. We verify our approach in two domains---including a high-dimensional video game environment requiring function approximation---where an agent first learns a set of base skills, and then composes them to solve a super-exponential number of new tasks.