Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes

DOI10.1109/LICS.2015.32MaRDI QIDQ4635808zbMATH OpenOpenAlexFDO

Authors Krishnendu Chatterjee, Zuzana Komárková, Jan Křetínský

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/1502.00611

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Markov and semi-Markov decision processes (90C40) Other game-theoretic models (91A40) Semantics in the theory of computing (68Q55)

Abstract: We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. We consider optimization with respect to both objectives at once, thus unifying the existing semantics. Precisely, the goal is to optimize the expectation while ensuring the satisfaction constraint. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensure certain probabilistic guarantee). Our main results are as follows: First, we present algorithms for the decision problems which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Second, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.

Recommendations

• Unifying two views on multiple mean-payoff objectives in Markov decision processes
• Markov Decision Processes with Multiple Objectives
• Multi-objective discounted Markov decision processes with expectation and variance criteria
• Multiple objective nonatomic Markov decision processes with total reward criteria
• scientific article; zbMATH DE number 4003940
• Markov Decision Processes with Multiple Long-Run Average Objectives
• Markov decision processes with multiple long-run average objectives
• scientific article; zbMATH DE number 3852821
• On Finding Optimal Policies for Markov Decision Chains: A Unifying Framework for Mean-Variance-Tradeoffs
• Mixing probabilistic and non-probabilistic objectives in Markov decision processes

Cited in

(10)

• Optimizing the expected mean payoff in energy Markov decision processes
• Percentile queries in multi-dimensional Markov decision processes
• Combinations of Qualitative Winning for Stochastic Parity Games
• Learning-based mean-payoff optimization in an unknown MDP under omega-regular constraints
• Compositional strategy synthesis for stochastic games with multiple objectives
• An extended ϵ‐constraint method for a multiobjective finite‐horizon Markov decision process
• Unifying two views on multiple mean-payoff objectives in Markov decision processes
• Efficient strategy iteration for mean payoff in Markov decision processes
• Hedging bets in Markov decision processes
• Markov decision processes with multiple long-run average objectives

This page was built for publication: Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes

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