Policy Synthesis for Interval MDPs via Polyhedral Lyapunov Functions

Negar Monir, Sadegh Soudjani

This paper, recently published by researchers from Newcastle University, the Max Planck Institute, and the University of Birmingham, tackles the complex challenge of making robust decisions when faced with multiple competing goals and uncertain data.

TL;DR

The authors introduce a novel framework for synthesizing policies in Multi-Objective Interval Markov Decision Processes (MOIMDPs) by using Polyhedral Lyapunov Functions. By treating value iteration as a switched affine system, they provide a way to reach target performance goals with formal convergence guarantees, avoiding the computationally "expensive" need to calculate entire Pareto curves.

What Problem Does This Paper Address?

In autonomous systems, robotics, and healthcare, we often use Markov Decision Processes (MDPs) to model decision-making. However, real-world scenarios present two major hurdles:

  1. Multiple Objectives: A self-driving car must balance safety, speed, and fuel efficiency.
  2. Interval Uncertainty: We rarely know exact transition probabilities (e.g., "there is exactly a 70.2% chance the robot moves forward"). Instead, we have ranges or intervals (e.g., "between 65% and 75%").

Standard approaches for Multi-Objective IMDPs (MOIMDPs) usually try to compute a Pareto curve—a set of all optimal trade-offs. This is often computationally impossible to do exactly. Previous attempts to simplify this using Lyapunov stability theory relied on quadratic functions (which create ellipsoidal "safe zones"). These ellipsoids are often too "smooth" and conservative, failing to capture the sharp, piecewise-linear nature of the underlying math, which leads to imprecise policies or outright failure in complex scenarios.

Methods

The authors propose a shift from "round" (quadratic) to "sharp" (polyhedral) geometry. Their approach involves several key steps:

  • Reformulation as a Switched Affine System: They represent the Value Iteration (VI) algorithm—the standard way to solve MDPs—as a discrete-time switched affine system (dt-SAS). In this view, different policies are "switches," and the rewards/transitions are "affine" transformations.
  • Polyhedral Lyapunov Functions (PLFs): Instead of using ellipsoids to define the region where the system is stable, they use polyhedra. These shapes have adjustable facets that can align much more closely with the boundaries of the uncertainty intervals.
  • CEGIS (Counterexample-Guided Inductive Synthesis): To find the right PLF, they use a loop:
  • Synthesizer: Propose a candidate PLF and a "safe zone" (Invariant Set of Attraction).
  • Verifier: Use an SMT solver (like Z3) or an Optimization solver (like Gurobi/Mosek) to check if the system can "escape" this zone.
  • Refinement: If a "counterexample" (a way to escape) is found, the math is refined, and the loop repeats until the zone is proven stable.
  • Direct Targeting: Instead of finding every possible trade-off, the user provides a target performance value, and the algorithm finds a policy that brings the system into a tight neighborhood of that target.

Datasets

The methodology was validated using three distinct case studies:

  1. Recycling Robot: A classic MDP benchmark involving a robot collecting cans and deciding when to recharge.
  2. 3-State IMDP: A standard synthetic benchmark from existing literature used to test interval uncertainty.
  3. EV Battery Life Cycle: A more complex 6-state model with three objectives: minimizing economic cost, minimizing battery health penalties, and maximizing environmental benefits.

Key Insights and Ideas

  • Geometry Matters: The "aha moment" is that polyhedral functions are naturally better suited for the piecewise-affine structure of dynamic programming than quadratic ones. This allows for much "tighter" error bounds.
  • Avoiding the Pareto Trap: By focusing on a specific target set rather than the entire Pareto front, the authors bypass the most computationally grueling part of multi-objective optimization.
  • Formal Guarantees: Unlike many reinforcement learning approaches that are "black boxes," this method provides a mathematical certificate (the Lyapunov function) that the policy will converge to the desired target despite the uncertainty.

Key Results

  • Higher Accuracy: In the Electric Vehicle (EV) battery case study, the PLF-based methods (both SMT and Optimization versions) produced tighter error bands than the quadratic baseline.
  • Robustness to Infeasibility: For certain complex targets in the EV model, the traditional quadratic approach was infeasible (could not find a solution), whereas the polyhedral approach successfully synthesized a valid policy.
  • Computational Trade-off: While the PLF synthesis is more accurate, it is slower. Synthesis took several minutes (e.g., ~2000s for complex cases) compared to seconds for the quadratic method. However, once the policy is synthesized, the actual execution (Value Iteration) is extremely fast (2-4 seconds).

Limitations and Future Work

  • Scalability: The CEGIS loop relies on SMT and MILP solvers, which face exponential complexity growth as the number of states and objectives increases. The authors note that for very large-scale systems, this could become a bottleneck.
  • Constrained DP: The current work focuses on reaching a target. Future work aims to incorporate hard constraints (e.g., "never let the battery charge drop below X%") directly into the dynamic programming loop.
  • State Abstraction: To handle larger models, the authors suggest integrating abstraction methods to reduce the effective size of the state space before applying the PLF synthesis.

Summary updated

Abstract

Decision-making under uncertainty is central to many safety-critical applications, where decisions must be guided by probabilistic modeling formalisms. This paper introduces a novel approach to policy synthesis in multi-objective interval Markov decision processes using polyhedral Lyapunov functions. Unlike previous Lyapunov-based methods that mainly rely on quadratic functions, our method utilizes polyhedral functions to enhance accuracy in managing uncertainties within value iteration of dynamic programming. We reformulate the value iteration algorithm as a switched affine system with interval uncertainties and apply control-theoretic stability principles to synthesize policies that guide the system toward a desired target set. By constructing an invariant set of attraction, we ensure that the synthesized policies provide convergence guarantees while minimizing the impact of transition uncertainty in the underlying model. Our methodology removes the need for computationally intensive Pareto curve computations by directly determining a policy that brings objectives within a specified range of their target values. We validate our approach through numerical case studies, including a recycling robot and an electric vehicle battery, demonstrating its effectiveness in achieving policy synthesis under uncertainty.
BibTeX
@misc{monir2026policy,
  author = {Negar Monir and Sadegh Soudjani},
  title = {{Policy Synthesis for Interval MDPs via Polyhedral Lyapunov Functions}},
  year = {2026},
  eprint = {2601.03445},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.03445},
}
Figure