Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes
The beyond worst-case synthesis problem was introduced recently by Bruy\ere
et al. [BFRR14]: it aims at building system controllers that provide strict
worst-case performance guarantees against an antagonistic environment while
ensuring higher expected performance against a stochastic model of the
environment. Our work extends the framework of [BFRR14] and follow-up papers,
which focused on quantitative objectives, by addressing the case of
$\omega$-regular conditions encoded as parity objectives, a natural way to
represent functional requirements of systems.
We build strategies that satisfy a main parity objective on all plays, while
ensuring a secondary one with sufficient probability. This setting raises new
challenges in comparison to quantitative objectives, as one cannot easily mix
different strategies without endangering the functional properties of the
system. We establish that, for all variants of this problem, deciding the
existence of a strategy lies in ${\sf NP} \cap {\sf coNP}$, the same complexity
class as classical parity games. Hence, our framework provides additional
modeling power while staying in the same complexity class.
[BFRR14] V\'eronique Bruy\ere, Emmanuel Filiot, Mickael Randour, and
Jean-Fran\c{c}ois Raskin. Meet your expectations with guarantees: Beyond
worst-case synthesis in quantitative games. In Ernst W. Mayr and Natacha
Portier, editors, 31st International Symposium on Theoretical Aspects of
Computer Science, STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of
LIPIcs, pages 199-213. Schloss Dagstuhl - Leibniz - Zentrum fuer Informatik,
2014.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints
We formalize the problem of maximizing the mean-payoff value with high probability while satisfying a parity objective in a Markov decision process (MDP) with unknown probabilistic transition function and unknown reward …
Life is Random, Time is Not: Markov Decision Processes with Window Objectives
The window mechanism was introduced by Chatterjee et al. to strengthen classical game objectives with time bounds. It permits to synthesize system controllers that exhibit acceptable behaviors within a configurable time …
Fair regression under localized demographic parity constraints
Demographic parity (DP) is a widely used group fairness criterion requiring predictive distributions to be invariant across sensitive groups. While natural in classification, full distributional DP is often overly restri…
Quantitative Analysis of $ω$-Regular Robust MDPs
Robust Markov Decision Processes (RMDPs) generalize classical MDPs by allowing uncertainty in transition probabilities and optimizing against their worst-case realization. We consider $(s,a)$-rectangular RMDPs with \emph…
Retiring $Δ$DP: New Distribution-Level Metrics for Demographic Parity
Demographic parity is the most widely recognized measure of group fairness in machine learning, which ensures equal treatment of different demographic groups. Numerous works aim to achieve demographic parity by pursuing …
Fairness