🤖 AI

Composing Reinforcement Learning Policies, with Formal Guarantees

This paper proposes a novel framework that combines reactive synthesis for high-level planning with a reinforcement learning approach for low-level policy training on latent structures to compose controllers for complex, two-level environments while providing formal performance guarantees without requiring model distillation.

Original authors: Florent Delgrange, Guy Avni, Anna Lukina, Christian Schilling, Ann Nowé, Guillermo A. Pérez

Published 2026-08-06

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Florent Delgrange, Guy Avni, Anna Lukina, Christian Schilling, Ann Nowé, Guillermo A. Pérez

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to navigate a giant, shifting maze. This isn't just a simple maze; it's a world where the walls might move, the floor might change, and the robot has to make split-second decisions to avoid getting hit by flying obstacles. This is the world of Reinforcement Learning (RL), a branch of artificial intelligence where agents learn by trial and error, much like a dog learning to sit for a treat. The goal is to find a "policy"—a set of rules that tells the agent what to do in every situation to get the best result.

However, there is a catch. While RL is great at learning from experience, it is notoriously bad at giving guarantees. If you ask a standard RL robot, "Are you 100% sure you won't crash into that forklift?" it usually can't answer with a mathematical "yes." It might say, "I think I'll be okay," but in safety-critical jobs like driving cars or managing power grids, "I think" isn't good enough. This is where formal verification comes in. It's like a strict math proof that says, "Under these specific conditions, this action is guaranteed to be safe." The challenge scientists face is that these two worlds—learning from experience and mathematical proof—usually don't get along. Learning requires massive, messy data, while proofs require neat, simple models. This paper steps into that messy intersection to see if we can have our cake and eat it too: a robot that learns the hard stuff but still comes with a safety certificate.

The Big Idea: The Map and the Rooms

The authors, a team of researchers from Belgium, Israel, the Netherlands, Denmark, and the UK, propose a clever way to split the problem in two. Imagine a giant warehouse. The high-level view is a simple map: a grid of rooms connected by doors. You know the map perfectly. You know Room A connects to Room B, and Room B connects to the exit. But inside each room? That's a mystery. The "dynamics" (how things move, where the obstacles are) are unknown and chaotic.

The authors call this a two-level structure.

The High Level (The Map): This is the easy part. It's just a graph of rooms and doors.
The Low Level (The Rooms): This is the hard part. Inside each room, the agent has to dodge moving forklifts, workers, or other robots. The rules here are complex and unknown.

The paper's main trick is "separation of concerns." They use two different tools for the two different levels. For the high-level map, they use Reactive Synthesis. Think of this as a super-smart, logical planner that can look at the map and a set of rules (like "Get to the exit without hitting anything") and mathematically prove the best path to take. It's like a GPS that never gets lost because it has a perfect map.

But the GPS can't tell the robot how to dodge a forklift inside a room. For that, they use Reinforcement Learning (RL). The robot learns by running simulations inside each room, figuring out how to get from the entrance to the exit without crashing. The problem is, standard RL is a "black box"—you don't know exactly how it works, and you can't prove it's safe.

The Magic Trick: The "Latent" Shortcut

Here is where the paper gets really cool. Instead of just letting the robot learn a messy, giant neural network (a brain made of math) for each room, the authors teach the robot to learn a concise latent model.

Imagine you are trying to describe a chaotic room full of moving obstacles to a friend. You could try to describe every single movement of every single object, which would take forever and be impossible to remember. Or, you could create a simplified sketch (the "latent model") that captures the essence of the room: "If I go left, I usually hit a wall; if I go right, I usually find the door."

The authors developed a new training method called WAE-DQN. This is a fancy name for a process where the robot learns two things at the same time:

How to act (the policy).
How to draw the simplified sketch (the latent model).

Crucially, they don't just guess the sketch; they calculate a guarantee on how good the sketch is. They use something called PAC bounds (Probably Approximately Correct). Think of this as a "confidence score." It doesn't say "This sketch is perfect." It says, "We are 95% sure that this sketch is within 1% of the real room's behavior."

Putting It All Together: The Planner

Once the robot has learned these simplified sketches and the "confidence scores" for every room, the high-level planner kicks in. The planner looks at the map and the sketches. It asks: "If I send the robot into Room A and tell it to go right, what are the odds it makes it to the door?" It uses the confidence scores from the sketches to answer this mathematically.

Because the planner knows the "safety margin" of each room's sketch, it can build a global plan that is mathematically guaranteed to work, even though the robot learned the details of the rooms by trial and error.

The Experiments: Does It Work?

The team tested this idea in two very different worlds:

A Grid World: A digital maze with moving enemies.
ViZDoom: A video game environment (based on the classic Doom) where the robot has to navigate using visual inputs (like a camera) while dodging enemies.

In the Grid World, they created a maze with 9 rooms and 11 moving enemies. Standard AI (using a method called DQN) struggled to learn a good path, often getting stuck or crashing. But the new method? It learned to navigate successfully. Even more impressively, they tested it on a much bigger maze with 49 rooms and 47 enemies. The robot, using the same learned "sketches" from the small rooms, was able to navigate the giant maze successfully. This proves the "reusability" of their approach: once you learn how to handle a type of room, you can use that knowledge in any similar room, no matter how big the map gets.

In the ViZDoom experiment, the robot had to deal with visual inputs and shooting enemies. The results showed that the "latent values" (the predictions made by the simplified sketches) were very close to what actually happened in the real game. For example, when the robot predicted a 24% chance of success in a specific scenario, the actual success rate was around 23%. This closeness proves that the "sketches" were accurate enough to trust.

Why This Matters

The biggest win here isn't just that the robot got better at the game. It's that the robot got better with a safety certificate.

In the past, if you wanted a robot to navigate a complex environment, you had to choose between:

Safety: Using a simple model where you can prove everything is safe, but the robot is too dumb to handle real-world chaos.
Skill: Using a powerful learning robot that can handle chaos, but you have no idea if it will crash.

This paper shows a third way. By separating the "map" from the "rooms," and by teaching the robot to learn simplified, verified sketches of the rooms, they created a system that is both smart (it can handle moving obstacles and visual inputs) and safe (it comes with mathematical guarantees).

The authors admit that their method still needs a "map" of the environment to start with. They can't just throw a robot into a completely unknown world and expect it to build the map from scratch. But for environments where we know the layout (like a warehouse, a city grid, or a software system) but not the details of what happens inside the rooms, this approach offers a powerful new tool. It turns the "black box" of learning into a "glass box" that we can inspect, verify, and trust.

Technical Summary: Composing Reinforcement Learning Policies, with Formal Guarantees

Problem Formulation
The paper addresses the challenge of constructing control policies for environments with a two-level structure: a known high-level graph ("map") where each vertex is populated by a Markov Decision Process (MDP) with unknown dynamics, referred to as a "room." The objective is to satisfy a long-horizon task specified as a logical formula over the high-level map (e.g., "eventually reach vertex $T$ ") while navigating through these rooms.

The core difficulty lies in the trade-off between scalability and formal guarantees. Traditional reactive synthesis can provide formal guarantees for high-level tasks but requires explicit models of the entire environment, which is infeasible when room dynamics are unknown or high-dimensional. Conversely, Reinforcement Learning (RL) handles unknown, high-dimensional dynamics but generally lacks formal guarantees and struggles with sparse rewards in long-horizon tasks. The authors propose a framework that "separates concerns," applying reactive synthesis for the high-level planner and a novel RL procedure for low-level control, aiming to combine the scalability of RL with the formal guarantees of synthesis.

Methodology
The framework outputs a two-level controller consisting of a collection of low-level policies ( $\Pi$ ) and a high-level planner ( $\tau$ ).

Low-Level Learning (WAE-DQN):
Instead of training a policy directly on the raw environment and then distilling it into a model (a common two-step approach), the authors propose a unified, one-step procedure called WAE-DQN. This method simultaneously trains:
- A latent policy ( $\pi$ ) using Deep Q-Networks (DQN).
- A concise latent model (a small MDP) using Wasserstein Auto-Encoded MDPs (WAE-MDPs).
The latent model abstracts the room's state space via an embedding function $\phi$ . The training objective minimizes a transition loss ( $L_P$ ), which measures the discrepancy between the transition dynamics of the original environment and the latent model under the policy. This process yields "Probably Approximately Correct" (PAC) guarantees on the abstraction quality and policy performance without a separate distillation step.
High-Level Synthesis:
Given a map, a set of learned low-level policies (one for each room and exit direction), and a high-level specification, the authors synthesize a planner.
- They construct a succinct MDP ( $M^G_\Pi$ ) where states represent the direction of entry into a room, and actions represent the choice of the next exit direction.
- Transition probabilities in this succinct model are defined by the expected values (success probabilities) of the low-level latent policies.
- A standard planner is synthesized on this succinct model to maximize the high-level objective.
Lifting Guarantees:
A critical theoretical contribution is proving that guarantees learned locally for each room can be "lifted" to the global two-level controller. The authors show that if the initial distribution of each room provides sufficient state coverage during training, the value differences between the true environment and the abstracted controller are bounded. This allows the PAC bounds on individual room abstractions to translate into formal guarantees for the global planner.

Key Contributions
The paper outlines three primary theoretical contributions:

Learning Guarantees for Low-Level Policies: The authors establish a bound (Theorem 1) on the difference between the values of the latent model and the true environment based on the transition loss ( $L_P$ ). They further prove (Theorem 2) that these bounds are PAC learnable, providing a method to compute sample complexity for achieving a desired accuracy.
Guarantees on the Synthesized Controller: The paper proves memory bounds for the optimal high-level planner (Theorem 3), showing that a planner with memory size proportional to the number of vertices in the map is sufficient. Furthermore, it demonstrates (Theorem 4) that finding an optimal planner is equivalent to solving an MDP whose size depends only on the map structure, effectively ignoring the potentially massive size of the individual rooms.
Unified Learning and Synthesis Guarantees: The authors show (Theorem 5) that minimizing the loss function to learn abstractions independently for each room guarantees that the values obtained by the composed two-level controller in the abstraction closely match those in the true environment. This validates the "separation of concerns" approach.

Results and Case Studies
The authors validate their framework through two case studies involving an agent navigating environments with moving adversarial obstacles:

Grid World: A scalable grid environment with varying numbers of rooms and adversaries. Standard DQN with reward shaping struggled to find policies, whereas the proposed WAE-DQN successfully learned low-level reach-avoid objectives.
ViZDoom: A vision-based environment using the Doom game engine, featuring complex visual inputs and stochastic adversary behaviors.

In both studies, the synthesized two-level controller achieved high success probabilities, demonstrating the approach's ability to overcome sparse reward challenges. The predicted values in the latent models closely matched the empirical values observed in the true environments, confirming the quality of the learned abstractions. Notably, the low-level policies were shown to be reusable; the same set of policies trained on a smaller configuration performed effectively when the environment was scaled up (more rooms/adversaries) without retraining the low-level components.

Significance
The paper claims that its primary advantage is providing formal guarantees for controllers in environments where traditional synthesis does not scale due to unknown or complex low-level dynamics. By separating the high-level planning (handled by synthesis) from the low-level control (handled by RL with PAC guarantees), the framework reduces the engineering burden of reward shaping to local tasks only. It offers a remedy for the sparse reward problem in RL and enables the reusability of low-level policies across similar rooms or changing high-level tasks. The work bridges the gap between the scalability of deep RL and the rigor of formal methods, offering a path to verify and synthesize controllers for complex, multi-stage autonomous systems.