# Composing Reinforcement Learning Policies, with Formal Guarantees

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 33 of its 74 references that are in the map.
- First posted on arXiv 21 Feb 2024.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

## Builds on (most cited first, 30 of 33)

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://mlsanity.com/paper/1710.02298/) (2017)
- [Safe Reinforcement Learning via Shielding](https://mlsanity.com/paper/1708.08611/) (2017)
- [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020)
- [MADE: Masked Autoencoder for Distribution Estimation](https://mlsanity.com/paper/1502.03509/) (2015)
- [Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation](https://mlsanity.com/paper/1604.06057/) (2016)
- [A Practical Guide to Multi-Objective Reinforcement Learning and Planning](https://mlsanity.com/paper/2103.09568/) (2021)
- [DeepMDP: Learning Continuous Latent Space Models for Representation Learning](https://mlsanity.com/paper/1906.02736/) (2019)
- [ViZDoom: A Doom-based AI Research Platform for Visual Reinforcement Learning](https://mlsanity.com/paper/1605.02097/) (2016)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [Exploration in Deep Reinforcement Learning: A Survey](https://mlsanity.com/paper/2205.00824/) (2022)
- [Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints](https://mlsanity.com/paper/1404.7073/) (2014)
- [Sample-Efficient Multi-Objective Learning via Generalized Policy Improvement Prioritization](https://mlsanity.com/paper/2301.07784/) (2023)
- [Cautious Reinforcement Learning with Logical Constraints](https://mlsanity.com/paper/2002.12156/) (2020)
- [Safe Reinforcement Learning via Probabilistic Logic Shields](https://mlsanity.com/paper/2303.03226/) (2023)
- [Towards Scalable Verification of Deep Reinforcement Learning](https://mlsanity.com/paper/2105.11931/) (2021)
- [Learning Control Policies for Stochastic Systems with Reach-avoid Guarantees](https://mlsanity.com/paper/2210.05308/) (2022)
- [Steady State Analysis of Episodic Reinforcement Learning](https://mlsanity.com/paper/2011.06631/) (2020)
- [Robust Control for Dynamical Systems With Non-Gaussian Noise via Formal Abstractions](https://mlsanity.com/paper/2301.01526/) (2023)
- [Shielding Atari Games with Bounded Prescience](https://mlsanity.com/paper/2101.08153/) (2021)
- [Compositional Policy Learning in Stochastic Control Systems with Formal Guarantees](https://mlsanity.com/paper/2312.01456/) (2023)
- [Abstract Value Iteration for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2010.15638/) (2020)
- [Correct-by-Construction Runtime Enforcement in AI -- A Survey](https://mlsanity.com/paper/2208.14426/) (2022)
- [Formal Methods with a Touch of Magic](https://mlsanity.com/paper/2005.12175/) (2020)
- [Simple Strategies in Multi-Objective MDPs (Technical Report)](https://mlsanity.com/paper/1910.11024/) (2019)
- [Deep Abstract Q-Networks](https://mlsanity.com/paper/1710.00459/) (2017)

## Built on by (most cited first, 2 of 2)

- [Deep SPI: Safe Policy Improvement via World Models](https://mlsanity.com/paper/2510.12312/) (2025)
- [Value Functions as Supermartingale Certificates](https://mlsanity.com/paper/2605.31524/) (2026)

## Abstract (arXiv)

We propose a novel framework to controller design in environments with a two-level structure: a known high-level graph ("map") in which each vertex is populated by a Markov decision process, called a "room". The framework "separates concerns" by using different design techniques for low- and high-level tasks. We apply reactive synthesis for high-level tasks: given a specification as a logical formula over the high-level graph and a collection of low-level policies obtained together with "concise" latent structures, we construct a "planner" that selects which low-level policy to apply in each room. We develop a reinforcement learning procedure to train low-level policies on latent structures, which unlike previous approaches, circumvents a model distillation step. We pair the policy with probably approximately correct guarantees on its performance and on the abstraction quality, and lift these guarantees to the high-level task. These formal guarantees are the main advantage of the framework. Other advantages include scalability (rooms are large and their dynamics are unknown) and reusability of low-level policies. We demonstrate feasibility in challenging case studies where an agent navigates environments with moving obstacles and visual inputs.