Certified Policy Verification and Synthesis for MDPs under Distributional Reach-avoidance Properties

S. Akshay, Krishnendu Chatterjee, Tobias Meggendorfer, Dorde Zikelic

Abstract

Markov Decision Processes (MDPs) are a classical model for decision making in the presence of uncertainty. Often they are viewed as state transformers with planning objectives defined with respect to paths over MDP states. An increasingly popular alternative is to view them as distribution transformers, giving rise to a sequence of probability distributions over MDP states. For instance, reachability and safety properties in modeling robot swarms or chemical reaction networks are naturally defined in terms of probability distributions over states. Verifying such distributional properties is known to be hard and often beyond the reach of classical state-based verification techniques. In this work, we consider the problems of certified policy (i.e. controller) verification and synthesis in MDPs under distributional reach-avoidance specifications. By certified we mean that, along with a policy, we also aim to synthesize a (checkable) certificate ensuring that the MDP indeed satisfies the property. Thus, given the target set of distributions and an unsafe set of distributions over MDP states, our goal is to either synthesize a certificate for a given policy or synthesize a policy along with a certificate, proving that the target distribution can be reached while avoiding unsafe distributions. To solve this problem, we introduce the novel notion of distributional reach-avoid certificates and present automated procedures for (1) synthesizing a certificate for a given policy, and (2) synthesizing a policy together with the certificate, both providing formal guarantees on certificate correctness. Our experimental evaluation demonstrates the ability of our method to solve several non-trivial examples, including a multi-agent robot-swarm model, to synthesize certified policies and to certify existing policies.

Introduction

Guaranteeing the correct behavior of autonomous systems under uncertainty is a fundamental challenge, especially when dealing with populations of agents like robot swarms. Traditional analysis of Markov Decision Processes (MDPs) typically adopts a "state transformer" view, focusing on individual agent transitions. However, for large-scale systems, we often care about distributional properties—for example, ensuring 90% of a swarm reaches a goal while fewer than 10% enter a hazardous zone.

Reasoning about these properties using standard methods leads to a combinatorial explosion in the state space. Furthermore, verifying distributional properties is "Skolem-hard," making it a significant theoretical hurdle. This paper introduces a framework for "certified" control of MDPs by treating them as transformers of probability distributions. By synthesizing both a control policy and a mathematical "reach-avoid certificate," the authors provide formal, checkable proof that a system will reach a target distribution while strictly avoiding unsafe ones.

Methodology

The core of the approach is shifting the perspective to viewing MDPs as distribution transformers. Instead of tracking a single agent, the framework tracks how the entire probability distribution over states evolves over time.

A 2x4 grid world example used for distributional reach-avoidance tasks.

Distributional Reach-avoid Certificates

The authors define a certificate as a pair $(R, I)$:

  1. Distributional Invariant ($I$): A set of "safe" distributions within which the system is guaranteed to remain.
  2. Distributional Ranking Function ($R$): A mathematical construct that ensures progress toward the goal, preventing the system from getting stuck in infinite loops.

Synthesis via SMT Solving

To find these certificates, the authors use a template-based synthesis approach. They assume the policy and certificate can be described by linear (affine) equations with unknown coefficients. The requirements for a valid certificate are translated into a system of constraints. Using mathematical techniques like Farkas' Lemma and Handelman's Theorem for quantifier elimination, they convert complex logical statements into a format solvable by off-the-shelf SMT (Satisfiability Modulo Theories) solvers.

Experimental Evaluation

The method was evaluated on several benchmark models, including various Gridworld layouts (from 2x4 to 20x10), an Insulin pharmacokinetics model, and a PageRank-based Markov chain.

Experimental results for policy verification and synthesis across various MDP models.

Key Results

The prototype implementation, built in Python using the Yices SMT solver, demonstrated the following:

  • Verification Efficiency: The tool successfully solved 7 out of 7 policy verification tasks. Notably, it verified a policy for a large 20x10 grid (88 states, 280 actions) in just 68 seconds.
  • Synthesis Capability: It successfully synthesized both a policy and a certificate for 3 out of 5 complex synthesis tasks.
  • Scalability: The results show that SMT solvers can handle the constraints generated by this distributional approach for reasonably sized state spaces, bypassing the "curse of dimensionality" associated with multi-agent systems.

Discussion and Conclusion

A key insight of this work is the decoupling of agent count from complexity. Because the method reasons about the distribution over states, the verification complexity remains constant whether the swarm contains 10 or 10 million robots. The "Ranking Function" is critical for ensuring that the system doesn't just stay safe but actually reaches its target.

While powerful, the method currently depends on user-defined "template sizes" for the certificates. If the safe set is highly non-linear, simple affine templates may fail. Future work aims to explore more general distributional properties, such as those defined in Linear Temporal Logic (LTL), and to develop heuristics for automatic template selection.

Summary updated

Abstract

Markov Decision Processes (MDPs) are a classical model for decision making in the presence of uncertainty. Often they are viewed as state transformers with planning objectives defined with respect to paths over MDP states. An increasingly popular alternative is to view them as distribution transformers, giving rise to a sequence of probability distributions over MDP states. For instance, reachability and safety properties in modeling robot swarms or chemical reaction networks are naturally defined in terms of probability distributions over states. Verifying such distributional properties is known to be hard and often beyond the reach of classical state-based verification techniques. In this work, we consider the problems of certified policy (i.e. controller) verification and synthesis in MDPs under distributional reach-avoidance specifications. By certified we mean that, along with a policy, we also aim to synthesize a (checkable) certificate ensuring that the MDP indeed satisfies the property. Thus, given the target set of distributions and an unsafe set of distributions over MDP states, our goal is to either synthesize a certificate for a given policy or synthesize a policy along with a certificate, proving that the target distribution can be reached while avoiding unsafe distributions. To solve this problem, we introduce the novel notion of distributional reach-avoid certificates and present automated procedures for (1) synthesizing a certificate for a given policy, and (2) synthesizing a policy together with the certificate, both providing formal guarantees on certificate correctness. Our experimental evaluation demonstrates the ability of our method to solve several non-trivial examples, including a multi-agent robot-swarm model, to synthesize certified policies and to certify existing policies.
BibTeX
@inproceedings{akshay2024certified,
  author = {S. Akshay and Krishnendu Chatterjee and Tobias Meggendorfer and Dorde Zikelic},
  title = {{Certified Policy Verification and Synthesis for MDPs under Distributional Reach-avoidance Properties}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure