Distillation of RL Policies with Formal Guarantees via Variational Abstraction of Markov Decision Processes

Florent Delgrange, Ann Nowe, Guillermo PerezOpenReview 2023 · OpenReview

TL;DR

This paper introduces VAE-MDPs, a framework for learning verifiable, simplified models of complex, continuous-state Reinforcement Learning (RL) environments. By training a Variational Autoencoder (VAE) on data from a learned RL policy, they create a discrete latent model that approximates the original environment, enabling formal verification of the policy's behavior. This approach also yields a distilled, verifiable policy for the latent model.

What Problem Does This Paper Address?

Reinforcement learning (RL) has shown impressive results in various domains, but the learned policies often lack formal guarantees, making them unsuitable for safety-critical applications. This is especially true for deep RL methods operating in continuous environments, where theoretical convergence guarantees are lost. While formal methods exist for verifying policies in simpler, discrete Markov Decision Processes (MDPs), applying them to complex, unknown, continuous-state environments is challenging. The authors aim to bridge this gap by learning a verifiable, discrete abstraction of the continuous environment and distilling a policy for this abstraction.

Methods

The core of the proposed method, VAE-MDPs, involves training a Variational Autoencoder (VAE) to learn a discrete latent space model of the unknown continuous environment. This VAE is trained using data collected by an existing, pre-learned RL policy interacting with the environment. The VAE learns:

  • Discrete latent state and action spaces: Representing the continuous environment in a simpler, discrete form.
  • Embedding functions: Mapping between the original and latent state/action spaces.
  • A latent MDP: A simplified model of the environment dynamics in the latent space.
  • A distilled policy: A new policy trained to operate within the latent space.

The authors leverage the DeepMDP framework to derive bisimulation bounds, which quantify the similarity between the original and latent MDPs. These bounds allow for formal verification of the distilled policy's properties (like reachability and safety) using standard formal methods tools. They also introduce novel local loss functions and PAC (Probably Approximately Correct) guarantees for estimating these bounds from samples, making the approach practical. To combat posterior collapse in the VAE training, they employ prioritized experience replay and annealing schemes for regularization terms.

Datasets

The paper evaluates their approach on standard OpenAI Gym environments:

  • CartPole
  • MountainCar
  • Acrobot
  • Pendulum
  • LunarLander

These environments include both continuous states with discrete actions (CartPole, MountainCar, Acrobot) and continuous states with continuous actions (Pendulum, LunarLander).

Key Insights and Ideas

  • Bridging the gap between deep RL and formal verification: The paper provides a concrete method to make complex, deep RL policies verifiable by abstracting the environment into a discrete, manageable form.
  • VAE as a tool for formal methods: Demonstrates how VAEs can be used not just for representation learning but also for generating verifiable models of dynamic systems.
  • Bisimulation bounds for practical verification: The introduction of local bisimulation bounds and their PAC-efficient approximation allows for practical assessment of the learned abstraction's quality.
  • Prioritized experience replay for VAE stability: Using prioritized experience replay is shown to be crucial for preventing posterior collapse during VAE training, leading to more stable learning of latent representations.
  • Distilled policy for verifiability: The ability to distill a policy that operates in the latent space means that formal guarantees can be directly applied to this new, simplified policy.

Key Results

  • The VAE-MDP framework successfully learns discrete latent models that approximate unknown continuous environments.
  • The learned latent models exhibit bisimulation guarantees, indicating a good quality of abstraction.
  • The PAC bounds for local losses are computed, demonstrating the theoretical underpinnings for verifying the abstraction.
  • A distilled policy is obtained that achieves performance comparable to the original RL policy in the environment, while being verifiable in the latent space.
  • Experiments show that prioritized experience replay significantly improves the quality of learned latent spaces compared to uniform replay, preventing collapse into trivial representations.

Limitations and Future Work

  • Approximation of local losses: While PAC guarantees are provided, the authors acknowledge that the KL divergence is used as a proxy for the Wasserstein distance in the local loss calculation, which might not perfectly preserve theoretical guarantees. However, empirical results suggest it's a good proxy.
  • Assumption of ergodicity: The framework relies on the assumption that the MDP is ergodic, which is stated to be compliant with many RL environments but might restrict applicability in some cases.
  • Scalability of formal methods: While the framework enables formal verification, the scalability of the formal methods themselves to very large discrete latent spaces remains a challenge.
  • Future work: The authors suggest extending their approach to multi-agent systems and applying it to real-world case studies. They also highlight the potential for combining their method with existing safe-RL approaches that require an abstract model of the environment.

Summary updated

Abstract

We consider the challenge of policy simplification and verifi- cation in the context of policies learned through reinforce- ment learning (RL) in continuous environments. In well- behaved settings, RL algorithms have convergence guaran- tees in the limit. While these guarantees are valuable, they are insufficient for safety-critical applications. Furthermore, they are lost when applying advanced techniques such as deep- RL. To recover guarantees when applying advanced RL algo- rithms to more complex environments with (i) reachability, (ii) safety-constrained reachability, or (iii) discounted-reward objectives, we build upon the DeepMDP framework to derive new bisimulation bounds between the unknown environment and a learned discrete latent model of it. Our bisimulation bounds enable the application of formal methods for Markov decision processes. Finally, we show how one can use a pol- icy obtained via state-of-the-art RL to efficiently train a vari- ational autoencoder that yields a discrete latent model with provably approximately correct bisimulation guarantees. Ad- ditionally, we obtain a distilled version of the policy for the latent model.
BibTeX
@misc{delgrange2023distillation,
  author = {Florent Delgrange and Ann Nowe and Guillermo Perez},
  title = {{Distillation of RL Policies with Formal Guarantees via Variational Abstraction of Markov Decision Processes}},
  year = {2023},
  url = {https://openreview.net/forum?id=VlAhog0RGU},
  howpublished = {OpenReview},
}
Figure