Percentile Queries in Multi-Dimensional Markov Decision Processes

2014/10/17 by Randour, Mickael, Raskin, Jean-François, Sankur, Ocan · 5 citations
#FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1410.4801

Abstract

Markov decision processes (MDPs) with multi-dimensional weights are useful to analyze systems with multiple objectives that may be conflicting and require the analysis of trade-offs. We study the complexity of percentile queries in such MDPs and give algorithms to synthesize strategies that enforce such constraints. Given a multi-dimensional weighted MDP and a quantitative payoff function f, thresholds v_i (one per dimension), and probability thresholds α_i, we show how to compute a single strategy to enforce that for all dimensions i, the probability of outcomes ρ satisfying f_i(ρ) ≥ v_i is at least α_i. We consider classical quantitative payoffs from the literature (sup, inf, lim sup, lim inf, mean-payoff, truncated sum, discounted sum). Our work extends to the quantitative case the multi-objective model checking problem studied by Etessami et al. in unweighted MDPs.

Cited by

• Multi-Objective Statistical Model Checking using Lightweight Strategy Sampling (extended version)
• Certificates and Witnesses for Multi-objective ω-regular Queries in Markov Decision Processes
• Simplicity Lies in the Eye of the Beholder: A Strategic Perspective on Controllers in Reactive Synthesis
• Efficient Probabilistic Model Checking for Relational Reachability (Extended Version)
• Risk-aware Markov Decision Processes Using Cumulative Prospect Theory

Related

• Simple Strategies in Multi-Objective MDPs (Technical Report)
• MDP Geometry, Normalization and Reward Balancing Solvers
• The Value Problem for Multiple-Environment MDPs with Parity Objective
• Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives
• Efficiently Solving Discounted MDPs with Predictions on Transition Matrices