Multidimensional beyond worst-case and almost-sure problems for mean-payoff objectives

DOI10.1109/LICS.2015.33MaRDI QIDQ4635809zbMATH OpenOpenAlexFDO

Authors Lorenzo Clemente, Jean-François Raskin

Publication date 23 April 2018

Published in 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.08211

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Markov and semi-Markov decision processes (90C40) Games involving graphs (91A43)

Abstract: The beyond worst-case threshold problem (BWC), recently introduced by Bruy`ere et al., asks given a quantitative game graph for the synthesis of a strategy that i) enforces some minimal level of performance against any adversary, and ii) achieves a good expectation against a stochastic model of the adversary. They solved the BWC problem for finite-memory strategies and unidimensional mean-payoff objectives and they showed membership of the problem in NP$cap$coNP. They also noted that infinite-memory strategies are more powerful than finite-memory ones, but the respective threshold problem was left open. We extend these results in several directions. First, we consider multidimensional mean-payoff objectives. Second, we study both finite-memory and infinite-memory strategies. We show that the multidimensional BWC problem is coNP-complete in both cases. Third, in the special case when the worst-case objective is unidimensional (but the expectation objective is still multidimensional) we show that the complexity decreases to NP$cap$coNP. This solves the infinite-memory threshold problem left open by Bruy`ere et al., and this complexity cannot be improved without improving the currently known complexity of classical mean-payoff games. Finally, we introduce a natural relaxation of the BWC problem, the beyond almost-sure threshold problem (BAS), which asks for the synthesis of a strategy that ensures some minimal level of performance with probability one and a good expectation against the stochastic model of the adversary. We show that the multidimensional BAS threshold problem is solvable in P.

Recommendations

• Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games
• Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games
• Threshold constraints with guarantees for parity objectives in Markov decision processes

Cited in

(8)

• Finite-memory strategy synthesis for robust multidimensional mean-payoff objectives
• Threshold constraints with guarantees for parity objectives in Markov decision processes
• Expectations or guarantees? I want it all! A crossroad between games and MDPs
• Learning-based mean-payoff optimization in an unknown MDP under omega-regular constraints
• Extending finite-memory determinacy to multi-player games
• scientific article; zbMATH DE number 7447747 (Why is no real title available?)
• scientific article; zbMATH DE number 7561341 (Why is no real title available?)
• Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games

This page was built for publication: Multidimensional beyond worst-case and almost-sure problems for mean-payoff objectives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635809)