Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games

DOI10.1016/j.ic.2016.10.011zbMath1371.91022OpenAlexW2555847713MaRDI QIDQ528191

Véronique Bruyère, Mickael Randour, Jean-François Raskin, Emmanuel Filiot

Publication date: 12 May 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2014/4458/

zbMATH Keywords

shortest pathMarkov decision processbeyond worst-case synthesismean-payofftwo-player quantitative game on graphworst-case and expected value

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Markov and semi-Markov decision processes (90C40)

Related Items (12)

Simple Strategies in Multi-Objective MDPs ⋮ Synthesis for Multi-weighted Games with Branching-Time Winning Conditions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Combinations of Qualitative Winning for Stochastic Parity Games ⋮ Unnamed Item ⋮ Quantitative reductions and vertex-ranked infinite games ⋮ Unnamed Item ⋮ Timed games with bounded window parity objectives

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Faster algorithms for mean-payoff games
• The complexity of the \(K\)th largest subset problem and related problems
• On short paths interdiction problems: Total and node-wise limited interdiction
• Fast convergence to state-action frequency polytopes for MDPs
• Positional strategies for mean payoff games
• Borel determinacy
• Minimizing risk models in Markov decision processes with policies depending on target values
• The complexity of mean payoff games on graphs
• Hoeffding's inequality for uniformly ergodic Markov chains
• Strategy synthesis for multi-dimensional quantitative objectives
• The complexity of multi-mean-payoff and multi-energy games
• Looking at mean-payoff and total-payoff through windows
• Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games
• Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition
• PP is as Hard as the Polynomial-Time Hierarchy
• Mean-Payoff Games with Partial-Observation
• On Time with Minimal Expected Cost!
• Energy and Mean-Payoff Games with Imperfect Information
• Games through Nested Fixpoints
• An Analysis of Stochastic Shortest Path Problems
• Lower Bounds for Selection in X + Y and Other Multisets
• A note on the complexity of cryptography (Corresp.)
• The complexity of probabilistic verification
• Multidimensional beyond Worst-Case and Almost-Sure Problems for Mean-Payoff Objectives
• Percentile performance criteria for limiting average Markov decision processes
• Variations on the Stochastic Shortest Path Problem
• Trading Performance for Stability in Markov Decision Processes
• Mathematical Foundations of Computer Science 2004
• Probability Inequalities for Sums of Bounded Random Variables
• Stochastic Games with Perfect Information and Time Average Payoff
• Percentile queries in multi-dimensional Markov decision processes

This page was built for publication: Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games