Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games
From MaRDI portal
Publication:528191
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/
shortest pathMarkov decision processbeyond worst-case synthesismean-payofftwo-player quantitative game on graphworst-case and expected value
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
