Compositional Policy Learning in Stochastic Control Systems with Formal
  Guarantees
Đorđe Žikelić Mathias Lechner Abhinav Verma Krishnendu Chatterjee Thomas A. Henzinger
Reinforcement learning has shown promising results in learning neural network
policies for complicated control tasks. However, the lack of formal guarantees
about the behavior of such policies remains an impediment to their deployment.
We propose a novel method for learning a composition of neural network policies
in stochastic environments, along with a formal certificate which guarantees
that a specification over the policy's behavior is satisfied with the desired
probability. Unlike prior work on verifiable RL, our approach leverages the
compositional nature of logical specifications provided in SpectRL, to learn
over graphs of probabilistic reach-avoid specifications. The formal guarantees
are provided by learning neural network policies together with reach-avoid
supermartingales (RASM) for the graph's sub-tasks and then composing them into
a global policy. We also derive a tighter lower bound compared to previous work
on the probability of reach-avoidance implied by a RASM, which is required to
find a compositional policy with an acceptable probabilistic threshold for
complex tasks with multiple edge policies. We implement a prototype of our
approach and evaluate it on a Stochastic Nine Rooms environment.