Compositional Reinforcement Learning

Definition

Compositional reinforcement learning builds a larger RL system from smaller learned components, subtasks, options, reward machines, shields, or subsystem policies whose interfaces make composition explicit.

Why It Matters

Large safety-critical tasks are often too opaque for monolithic end-to-end RL to verify. Compositional structure can expose entry conditions, exit conditions, task stages, local guarantees, or reusable skills so that training, testing, and verification can focus on smaller pieces while still supporting system-level claims.

Formalism / Key Objects

• Neary et al.’s subsystem schema is:

$$c=(I_c,F_c,T_c,{\pi }_c),$$

where I_c is an entry set, F_c is an exit set, T_c is a time horizon, and pi_c is the learned policy.

• A subtask success condition can be written:

$$P_s^{M,{\pi }_c}({◊}_{\le T_c}{F}_c)\ge p_c\text{for all }s\in I_c.$$

• A high-level meta-policy chooses which subsystem to execute next; the chosen subsystem runs until it reaches an exit condition or exhausts its time horizon.
• In ICRL pMDP Specification Decomposition, a high-level pMDP uses one parameter p_c per subsystem to represent a lower bound on successful subtask completion.
• Reward-machine approaches compose through finite task automata; shield-composition approaches compose through local safety obligations; pMDP approaches compose through probabilistic subsystem-success interfaces.

Connections

• Neary2022 - Verifiable and Compositional Reinforcement Learning Systems provides a pMDP route for decomposing probabilistic reachability specifications into subtask specifications.
• Probabilistic Model Checking supplies the reachability and MDP verification language used by high-level models.
• Reward Machines decompose temporally extended rewards and tasks into automaton states, which is a different but related route to compositional RL.
• Non-Markovian Reinforcement Learning often becomes compositional when task histories are represented as automata, reward machines, or hierarchical subtasks.
• Safe Reinforcement Learning benefits from compositionality when safety requirements can be checked locally and lifted to a system-level guarantee.
• Distributed Shield Synthesis is a compositional enforcement approach: it composes local shields and assume-guarantee obligations rather than learned subsystem success probabilities.

Common Confusions

• Compositional RL is not automatically safe; the guarantee depends on correct interfaces and trustworthy local performance bounds.
• Hierarchical RL can be compositional for sample efficiency without providing formal verification. Neary et al.’s contribution is specifically the verification-oriented high-level model.
• A high-level model can predict system success only to the extent that its subsystem parameters lower-bound real subsystem behavior.

Key Sources

• Neary2022 - Verifiable and Compositional Reinforcement Learning Systems
• Toro Icarte2022 - Reward Machines
• Furelos-Blanco2023 - Hierarchies of Reward Machines
• Brorholt2025 - Compositional Shielding and Reinforcement Learning for Multi-Agent Systems