Source-linked AI summary
Multi-Objective Model Checking of Markov Decision Processes
Kousha Etessami, Marta Kwiatkowska, Moshe Y. Vardi, Mihalis Yannakakis
TL;DR
The paper asks whether MDP strategies can simultaneously meet probability thresholds for multiple ω-regular objectives and how their trade-offs can be characterized. It reduces achievability to reachability and linear programming, while using graph-theoretic methods for qualitative queries. The resulting algorithms are polynomial in MDP size, approximate Pareto curves efficiently, and may produce strategies requiring randomization and memory.
Problem
The problem is deciding simultaneous probability achievability for multiple ω-regular objectives and representing their potentially infinite trade-off curves.
Method
The paper reduces multiple ω-regular achievability to reachability and multi-objective linear programming, and analyzes qualitative queries graph-theoretically.
Results
The algorithms decide achievability and produce strategies in polynomial time in MDP size, compute ε-approximate Pareto curves polynomially in MDP size and 1/ε, and handle broader multi-objective queries.
Takeaways & Limitations
Multi-objective MDP verification supports quantitative trade-off analysis, compositional reasoning, and qualitative queries, with strategies that may require randomization and memory.
Takeaways & Limitations
Exact Pareto representations cannot generally be constructed in polynomial time because the Pareto set can have superpolynomial size.
Abstract
from arXiv · showhide
We study and provide efficient algorithms for multi-objective model checking problems for Markov Decision Processes (MDPs). Given an MDP, M, and given multiple linear-time (ω-regular or LTL) properties \varphi\_i, and probabilities r\_i ε[0,1], i=1,...,k, we ask whether there exists a strategy σfor the controller such that, for all i, the probability that a trajectory of M controlled by σsatisfies \varphi\_i is at least r\_i. We provide an algorithm that decides whether there exists such a strategy and if so produces it, and which runs in time polynomial in the size of the MDP. Such a strategy may require the use of both randomization and memory. We also consider more general multi-objective ω-regular queries, which we motivate with an application to assume-guarantee compositional reasoning for probabilistic systems. Note that there can be trade-offs between different properties: satisfying property \varphi\_1 with high probability may necessitate satisfying \varphi\_2 with low probability. Viewing this as a multi-objective optimization problem, we want information about the "trade-off curve" or Pareto curve for maximizing the probabilities of different properties. We show that one can compute an approximate Pareto curve with respect to a set of ω-regular properties in time polynomial in the size of the MDP. Our quantitative upper bounds use LP methods. We also study qualitative multi-objective model checking problems, and we show that these can be analysed by purely graph-theoretic methods, even though the strategies may still require both randomization and memory.
1. Introduction
The paper develops polynomial-time algorithms for multi-objective model checking of MDPs, addressing simultaneous ω-regular objectives, trade-offs, and qualitative queries. It also provides polynomial-time approximation of Pareto curves and supports more general queries motivated by compositional reasoning.
- Motivation: MDPs model stochastic, probabilistic, and controlled behavior, with linear-time model checking traditionally maximizing the probability of one ω-regular or LTL property.
- Motivation: Multiple properties may trade off, so the paper studies simultaneously achievable probability vectors and their Pareto curve.
- Pareto approximation: An ε-approximate Pareto curve represents achievable vectors closely enough to avoid computing an exact curve that may contain infinitely many points.
- Quantitative methods: The core algorithm decides achievability for multiple ω-regular properties, produces a suitable strategy, and runs in polynomial time in the MDP size.It reduces multiple ω-regular objectives to multiple reachability objectives, then to multi-objective linear programming.
- General queries: Quantitative achievability and Pareto approximation use linear-programming methods, while general multi-objective queries can encode assume-guarantee compositional reasoning.
- Qualitative queries: Qualitative multi-objective queries are decidable in polynomial time using graph-theoretic techniques, although satisfying strategies may require randomization and memory.
2. Basics and background
This section defines finite-state MDPs, strategies, ω-regular objectives, achievable value vectors, and Pareto sets. It then outlines the paper’s polynomial-size model-checking algorithms, approximation approach, query reduction, compositional motivation, and strategy requirements.
- MDP and strategy basics: An MDP has states, enabled actions, and probabilistic transitions; fixing an initial state and strategy induces a probability space over infinite runs.Strategies may randomize over enabled actions, and transition probabilities for each enabled action sum to one.
- MDP and strategy basics: A strategy maps finite play histories to distributions over currently enabled actions, with pure and memoryless strategies as special cases.The paper represents strategy-controlled behavior using a derived Markov chain whose states are play histories.
- Objectives and Pareto sets: For properties expressed as LTL formulas or Büchi automata, the value vector records each property’s probability under a strategy, and the achievable set contains vectors dominated by some strategy value.The Pareto curve consists of achievable vectors not dominated by any distinct achievable vector.
- Objectives and Pareto sets: The Pareto curve is generally infinite and may contain n^Ω(log n) vertices for two reachability objectives in an MDP with n states and size O(n).This rules out exact polynomial-time construction in general, because the Pareto representation can have superpolynomial size.
- Algorithms and approximation: The paper computes an ε-approximate Pareto curve, where every achievable vector is almost dominated by an achievable vector in the approximation, using the relation r ≤ (1 + ε)t.Quantitative achievability is reduced first to multiple reachability objectives and then to multi-objective linear programming.
- Algorithms and strategy requirements: Quantitative queries use extended achievability reductions, while qualitative queries use polynomial-time graph-theoretic algorithms; both settings may require finite memory and randomization.General queries are motivated by assume-guarantee compositional reasoning for probabilistic systems, and fixed-query reductions may still be exponential in query size.
3. Multi-objective reachability
The section reduces multi-objective reachability to linear programming after preprocessing the MDP, establishing polynomial-time achievability and approximate Pareto-curve algorithms.
- Problem formulation: Reachability objectives maximize the probabilities of eventually reaching possibly overlapping target sets F_i.The MDP is cleaned up by removing states from which no target is reachable.
- Strategy structure: A memoryless strategy exists for satisfying the reachability thresholds whenever any strategy exists in a cleaned-up MDP.The construction may use randomized memoryless strategies, while the broader model-checking reductions can require memory.
- LP formulation: The multi-objective LP uses variables representing expected visits to target states and expected state-action usage.Feasibility of this LP is linked to the existence of a strategy satisfying the reachability requirements.
- LP formulation: The LP correspondence is proved by showing that strategy-induced occupancy values are finite and satisfy the LP constraints.The proof uses the substochastic transition matrix on non-target states and its convergent fundamental matrix.
- Algorithms and complexity: Polynomial time suffices to decide extended achievability queries and construct a memoryless satisfying strategy.For ε > 0, an ε-approximate Pareto curve for reachability objectives is computable in time polynomial in |M| and 1/ε.
4. Qualitative multi-objective model checking
Qualitative multi-objective queries are decided by graph-theoretic analysis of a product MDP, with strategies that may switch between phases and use memory and randomization.
- Algorithm: The algorithm decides qualitative multi-objective queries and constructs a satisfying strategy in polynomial time using only graph-theoretic methods.It avoids linear programming.
- Product construction: The construction forms a product MDP with naively determinized Büchi automata for the qualitative properties.Product states combine an MDP state with sets of automaton states updated according to successor labels.
- Strategy construction: A two-phase strategy first explores the retained MDP and then switches to a property-specific strategy upon reaching an appropriate target state.The switch occurs with nonzero probability at states associated with almost-sure or positive-probability objectives.
- Algorithm: The algorithm prunes states and actions that cannot reach the target region required for almost-sure properties.It then restricts the product MDP to reachable non-bad states and checks that every positive-probability property retains a target state.
- Correctness: The resulting strategy satisfies all almost-sure properties with probability 1 and each positive-probability property with positive probability.All bottom strongly connected components contain a target for the almost-sure property set, ensuring eventual phase switching almost surely.
5. Quantitative multi-objective model checking.
Quantitative multi-objective model checking reduces ω-regular properties to reachability objectives in a product MDP, yielding polynomial-time decision and approximate Pareto-curve procedures.
- Decision procedure: Quantitative multi-objective queries can be decided, with a satisfying strategy constructed, in time polynomial in the size of the MDP.The result applies to general quantitative multi-objective queries.
- Pareto approximation: Given ω-regular properties, the method constructs an ε-approximate Pareto curve in time polynomial in |M| and 1/ε.The achievable probability vectors are transferred to a reachability problem in a product MDP.
- Reduction: The reduction adds absorbing states s_R for property subsets R and associates each property ϕ_i with the targets s_R where ϕ_i belongs to R.Actions from product states enter an appropriate absorbing subset state when its corresponding target condition is available.
- Reduction: Achievable vectors are preserved between the original MDP and the reduced reachability MDP, and strategies can be recovered in both directions.This correspondence enables the reachability results to establish both quantitative model-checking conclusions.
- Optimization view: The Pareto frontier is characterized through weighted sums of property-satisfaction probabilities and the achievable set of memoryless strategies.A separating nonnegative weight vector supports the reduction from achievability to expected-reward optimization.
6. Concluding remarks
The paper notes improved approximation algorithms for the multi-objective MDP problems and outlines practical alternatives to LP-based methods. A broader compositional framework for probabilistic systems remains future work.
- Improved approximation results yield significantly better algorithms for the multi-objective linear-programming and MDP problems studied in the paper.The improvements are particularly notable in the bi-objective case.
- Value iteration and policy iteration can provide black-box optimization routines for approximating the Pareto curve, though without the same theoretical complexity guarantees.These methods can be combined with the paper’s approximation framework in practice.
- A full general compositional framework for probabilistic systems requires a separate paper and is planned as follow-up work.