Percentile queries in multi-dimensional Markov decision processes

DOI10.1007/s10703-016-0262-7zbMath1360.68518MaRDI QIDQ5892424

Ocan Sankur, Mickael Randour, Jean-François Raskin

Publication date: 15 May 2017

Published in: Formal Methods in System Design (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10703-016-0262-7

zbMATH Keywords

Markov decision processes; percentile queries; quantitative objectives

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C40: Markov and semi-Markov decision processes

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The complexity of membership problems for circuits over sets of integers
• The complexity of the \(K\)th largest subset problem and related problems
• Fast convergence to state-action frequency polytopes for MDPs
• Minimizing risk models in Markov decision processes with policies depending on target values
• Optimal threshold probability in undiscounted Markov decision processes with a target set.
• Strategy synthesis for multi-dimensional quantitative objectives
• Looking at mean-payoff and total-payoff through windows
• Minimising a threshold probability in discounted Markov decision processes
• Concurrent games with tail objectives
• Multi-objective Discounted Reward Verification in Graphs and MDPs
• PP is as Hard as the Polynomial-Time Hierarchy
• The Odds of Staying on Budget
• Multi-Objective Model Checking of Markov Decision Processes
• Probabilistic Systems with LimSup and LimInf Objectives
• An Analysis of Stochastic Shortest Path Problems
• Lower Bounds for Selection in X + Y and Other Multisets
• Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes
• The Target Discounted-Sum Problem
• Percentile performance criteria for limiting average Markov decision processes
• Computing Quantiles in Markov Reward Models
• Markov decision processes associated with two threshold probability criteria
• Variations on the Stochastic Shortest Path Problem
• Exact and Approximate Determinization of Discounted-Sum Automata
• Markov Decision Processes with Multiple Long-run Average Objectives
• Markov Decision Processes with Multiple Objectives
• Percentile queries in multi-dimensional Markov decision processes