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

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

Introduction

Traditional analysis of Markov Decision Processes (MDPs) typically centers on the behavior of a single agent. However, in domains such as swarm robotics or chemical reaction networks, the focus shifts to the collective behavior of a large population. Modeling such systems using standard state-based methods leads to a "state-space explosion," where complexity grows exponentially with the number of agents. This paper addresses the challenge of distributional reach-avoidance: ensuring a population distribution reaches a target set while avoiding unsafe regions.

Problem Formulation

The authors tackle the problem of managing populations by treating MDPs as distribution transformers. Instead of tracking individual paths, they analyze how a probability distribution over states evolves over time. The goal is to find a policy that guarantees the distribution stays within a safe set (avoidance) and eventually enters a target set (reachability). This problem is notoriously difficult and classified as "Skolem-hard," meaning no general algorithm is currently known to exist for all cases.

Methodology: Certificate-Based Verification and Synthesis

To provide formal guarantees, the researchers introduce a framework based on mathematical certificates consisting of a pair $(R, I)$:

  • Distributional Invariant ($I$): A set of distributions that the system is guaranteed to stay within, defining the "safe zone."
  • Distributional Ranking Function ($R$): A function mapping distributions to real numbers that must decrease at every step until the goal is reached, proving progress toward the target.

SMT-Based Implementation

The framework employs a template-based approach, assuming certificates and policies take an affine form (weighted sums of probabilities). The requirements for a valid certificate are translated into mathematical constraints. By applying a variant of Farkas' Lemma, the authors convert complex logic into a format compatible with off-the-shelf SMT (Satisfiability Modulo Theories) solvers.

Experimental Evaluation

The proposed method was evaluated on several benchmark models, including robot swarms in gridworlds of various sizes, an insulin pharmacokinetics model, and a PageRank model.

Figure 1: A gridworld benchmark illustrating the reach-avoid task with initial (I), obstacle (X), and goal (G) states.

The prototype tool, implemented in Python using SymPy and PySMT, demonstrated significant efficiency. Because the method reasons about distributions rather than individual agents, the computational cost remains independent of the population size.

Figure 2: Performance metrics for verification and synthesis across different benchmark models.

Key Results

  • Verification: The tool successfully solved all 7 verification tasks. For the largest 20x10 grid (88 states), verification was completed in 68 seconds.
  • Synthesis: The tool synthesized both policies and certificates for 3 out of 5 complex tasks.
  • Efficiency: Verification proved significantly faster than synthesis due to the simpler structure of SMT queries when the policy is predefined.

Discussion and Future Work

The current framework is "sound" (guaranteeing correctness if a certificate is found) and "relatively complete" for affine certificates. However, it faces limitations when the required certificate is highly complex or non-affine. Future work aims to automate the search for template sizes and explore more general distributional properties, potentially leading toward a "Distributional Linear Temporal Logic" (LTL).

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},
}

Loading related content...

Figure