A reinforcement learning agent can learn a handful of basic skills, such as "pick up something blue" or "pick up a square," and then solve many new tasks without further training by combining them with logic. "Blue AND square" becomes the pointwise minimum of the two skills' value estimates, "blue OR square" becomes the pointwise maximum, and "NOT blue" becomes a fixed linear flip. This idea, called Boolean task algebra, makes each new composed task free once the base skills exist. The base skills themselves are not free. The goal-conditioned value functions that make the algebra exact cost more to learn than ordinary ones, and every paper in this line either assumes they are pretrained or learns them from tasks that arrive in no chosen order. This note proposes a curriculum that decides which base skill to practice next. Each decision is scored by how many of the tasks the agent will eventually be asked to solve currently depend on that skill as their weakest link.
The proposal rests on a simple property of the algebra. The minimum and maximum operations, and the negation flip, never amplify errors: if each base value function is off by at most $\varepsilon_i$, a composed formula is off by at most the largest $\varepsilon_i$ among the bases it uses. The zero-shot quality of every target task is therefore set by a single bottleneck base. Because the formulas are known, the agent can compute without any rollouts which base is the bottleneck for how much of the target distribution. A curriculum can then spend environment steps where they lift the most target tasks over the success threshold. Practicing a skill that is already better than its partners in every formula buys nothing.
Core Claim
Our claim is that algebra-aware curricula reach a given fraction of zero-shot target-task success with substantially fewer environment steps than uniform or algebra-blind base-skill curricula. The claim is restricted to settings where base skills differ in difficulty or the target task distribution is skewed. When bases are symmetric and targets uniform, the method should reduce to round-robin, and we will show that it does. This restriction is part of the claim, not a hedge: the method predicts when ordering matters.
Background and Positioning
The method builds on the World Value Function construction of Composition and Zero-Shot Transfer with Lattice Structures in Reinforcement Learning and A Boolean Task Algebra for Reinforcement Learning.. Those papers formalize tasks as a Boolean lattice and prove exact zero-shot composition in deterministic environments. They also note that the upfront cost of learning these value functions exceeds that of a standard Q-function, which is the cost we attack.
The closest prior work is SOPGOL from Generalisation in Lifelong Reinforcement Learning through Logical Composition. SOPGOL checks whether an incoming task is expressible in its current skill library and adds a new base skill when it is not. Tasks reach it passively from an external stream. It never chooses what to practice, and it never asks which partially learned skill limits the most tasks.
Compositional Instruction Following with Language Models and Reinforcement Learning (CERLLA) parses language into Boolean formulas over pretrained base skills. It supplies our evaluation setting and target formula distribution, but it treats base acquisition as a sunk cost.
Two curriculum papers motivate the work without supplying the method. Why Do Animals Need Shaping? A Theory of Task Composition and Curriculum Learning proves, for linear compositions in a teacher-student model, that learning primitives before combinations yields speedups that grow exponentially with episode length. That result says "primitives first" but gives no rule for ordering primitives among themselves, and it does not cover the min/max structure of Boolean values. Environment Generation for Zero-Shot Compositional Reinforcement Learning (CoDE) builds curricula over sequential sub-task workflows and trains monolithic policies end to end. We keep modular values and compose them with fixed operators, so no environment generator is needed.
Self-Paced Deep Reinforcement Learning supplies one ingredient: the idea of pacing toward a target distribution. Its Gaussian context distributions do not fit a discrete space of logical formulas, a limitation the file notes explicitly.
Mechanism
Let $p(f)$ be a distribution over target formulas $f$. Each formula uses a set $B(f)$ of base skills. Let $\hat\varepsilon_i$ be the current estimated error of base skill $i$, measured either as the failure rate on held-out goals of that base task or as a Bellman-residual estimate. Nonexpansiveness gives the error bound for a formula's composed value:
$$\text{err}(f) \le \max_{j \in B(f)} \hat\varepsilon_j .$$
This bound is on the gap between the learned composition and the ideal composition of the true bases. In deterministic environments the ideal composition is optimal. In stochastic ones there is an additional gap that the curriculum cannot remove.
The curriculum assigns each base skill a priority:
$$\pi_i \propto \Delta_i \sum_f p(f)\,\mathbb{1}\Big[i = \arg\max_{j\in B(f)} \hat\varepsilon_j \ \text{and}\ \hat\varepsilon_i > \delta\Big]$$
Here $\Delta_i$ is the recent rate at which $\hat\varepsilon_i$ has been falling (the learning-progress term), and $\delta$ is the error level at which a composed task counts as solved. The sum is the target mass for which skill $i$ is the binding bottleneck. Multiplying by learning progress stops the agent from pouring steps into a bottleneck it cannot currently improve. Without that term, the method would show the stalling failure that the file attributes to regret-based generators.
Episodes for the chosen base skill use the standard extended-value learning procedure, with relabeling over goals. All target formulas are evaluated zero-shot by composition, with no training on them.
Research Program
The work has three parts. First, we implement the scheduler on top of an existing extended-value learner in discrete MiniGrid domains, together with the per-base error estimators. Second, we build controlled heterogeneity, because the hypothesis lives or dies on it. In PickUpObj MiniGrid we make some colors rare or place them behind doors so that their base skills are hard to learn. We then sweep target distributions from uniform to heavily skewed toward formulas involving hard attributes. Third, we move to the Augmented BabyAI suite of 162 compositional tasks, where the target distribution is fixed by CERLLA's instructions and parsing is held constant. The language parser is not part of our contribution, so we feed ground-truth formulas.
A secondary study tests the stochastic case. We add transition noise in Four Rooms and measure how much of the remaining error the bound fails to predict. This quantifies when the scheduler's model of the problem breaks down.
Baselines
The naive reference point is round-robin base training: equal environment steps per base skill, cycled, with the same learner, network, and total step budget. It is what prior work implicitly does when it pretrains bases. Beating it requires a statistically significant gain in area under the zero-shot target-success curve over at least five seeds in the heterogeneous settings. In symmetric settings we expect parity, and parity there is the predicted result, not a failure.
The strongest existing competitor is SOPGOL from Generalisation in Lifelong Reinforcement Learning through Logical Composition. We run it with tasks drawn from the same target distribution $p(f)$, so it receives the same information about what will be tested. We give it the same step budget and tune its novelty and jumpstart thresholds with the same number of trials we give our $\delta$ and progress window. It reports "100% initial performance" on PickUpObj composed tasks once pretrained on base tasks. That figure measures post-pretraining quality, not acquisition cost; we found no reported result on Lacuna for the environment steps needed to learn the base skills, which is the quantity we compare. Beating SOPGOL means reaching 90% target success in fewer steps.
On Augmented BabyAI, the reference numbers are from Compositional Instruction Following with Language Models and Reinforcement Learning: CERLLA matches an oracle success rate of 92%, and a non-compositional baseline reaches 80% after 21 million steps. We report the total steps, base acquisition included, needed to reach 80% and 92%. Our method succeeds if it reaches 80% well under 21 million steps and reaches 92% faster than CERLLA's bases trained round-robin.
The key ablation is an algebra-blind learning-progress curriculum. It keeps the same $\Delta_i$ term but replaces the bottleneck mass with a constant, so it prioritizes whichever base is improving fastest. This isolates the algebraic weighting. A second ablation replaces estimated errors with oracle errors computed by exhaustive evaluation, to separate scheduler design from estimation noise.
Why not just…?
Why not just train bases round-robin? This is the real threat. If base skills are similarly hard or the targets are uniform, the bottleneck weighting has nothing to exploit. We do not argue around this. The heterogeneity sweep measures how large the gain is as a function of base difficulty spread and target skew, and a flat curve would falsify the proposal.
Why not just use a learning-progress curriculum over base tasks? Progress-driven methods favor skills that are improving. Under min-composition, though, improving a skill that is already stronger than its partners leaves every target task unchanged. The algebra-blind ablation is exactly this alternative, and it should lose most clearly when a fast-improving base never appears as anyone's bottleneck.
Why not just train one goal-conditioned policy on the target tasks with a continuous curriculum such as SPDL, or end to end as in BabyAI? Such a policy must be trained on each task context rather than composing them. On 3D Point Mass, Self-Paced Deep Reinforcement Learning reports 9.35 reward for SPDL against 2.34 for ALP-GMM and 0.50 for GoalGAN, showing how fragile many curricula are. Its parametric contexts do not cover discrete formulas. BabyAI: A Platform to Study the Sample Efficiency of Grounded Language Learning reports 77% on BossLevel even with one million demonstrations, and it documents curriculum confusion. The 80%-at-21-million-steps non-compositional result is the concrete bar this alternative must clear.
Why not just practice composed tasks directly? Training on "blue OR square" also yields useful experience. We include a variant that samples composed tasks from $p(f)$ and back-propagates through the min/max composition to the bases. If it matches our scheduler, the contribution reduces to "train on the target distribution through the algebra," and we would report it that way.
Proposed Experiments
The decisive check is the heterogeneity sweep on PickUpObj MiniGrid, plotting the step savings over round-robin and over the algebra-blind ablation against base difficulty spread and target skew. The prediction is near-zero savings at the symmetric corner and growing savings toward the skewed, heterogeneous corner. A second check verifies the bound: across training, the composed-task failure rate should track the estimated error of the bottleneck base more closely than the mean error of the bases. If it does not, the scheduler's model is wrong even if it happens to win.
The BabyAI 162-task comparison against the 80% and 92% reference points tests whether the gain survives with visual inputs. The noisy Four Rooms study maps how quickly stochastic dynamics erode the gain, by measuring the composition gap that no ordering of base training can close.
References
- Composition and Zero-Shot Transfer with Lattice Structures in Reinforcement Learning
- A Boolean Task Algebra for Reinforcement Learning.
- Generalisation in Lifelong Reinforcement Learning through Logical Composition
- Compositional Instruction Following with Language Models and Reinforcement Learning
- Why Do Animals Need Shaping? A Theory of Task Composition and Curriculum Learning
- Environment Generation for Zero-Shot Compositional Reinforcement Learning
- Self-Paced Deep Reinforcement Learning
- BabyAI: A Platform to Study the Sample Efficiency of Grounded Language Learning