Trading performance for stability in Markov decision processes

DOI10.1016/J.JCSS.2016.09.009MaRDI QIDQ340568zbMATH OpenOpenAlexFDO

Authors Tomáš Brázdil, Krishnendu Chatterjee, Vojtech Forejt, Antonin Kučera

Publication date 14 November 2016

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

stabilitymean payoffMarkov decision processesstochastic systemscontroller synthesis

Mathematics Subject Classification ID

Markov and semi-Markov decision processes (90C40)

Abstract: We study the complexity of central controller synthesis problems for finite-state Markov decision processes, where the objective is to optimize both the expected mean-payoff performance of the system and its stability. We argue that the basic theoretical notion of expressing the stability in terms of the variance of the mean-payoff (called global variance in our paper) is not always sufficient, since it ignores possible instabilities on respective runs. For this reason we propose alernative definitions of stability, which we call local and hybrid variance, and which express how rewards on each run deviate from the run's own mean-payoff and from the expected mean-payoff, respectively. We show that a strategy ensuring both the expected mean-payoff and the variance below given bounds requires randomization and memory, under all the above semantics of variance. We then look at the problem of determining whether there is a such a strategy. For the global variance, we show that the problem is in PSPACE, and that the answer can be approximated in pseudo-polynomial time. For the hybrid variance, the analogous decision problem is in NP, and a polynomial-time approximating algorithm also exists. For local variance, we show that the decision problem is in NP. Since the overall performance can be traded for stability (and vice versa), we also present algorithms for approximating the associated Pareto curve in all the three cases. Finally, we study a special case of the decision problems, where we require a given expected mean-payoff together with zero variance. Here we show that the problems can be all solved in polynomial time.

Recommendations

• Trading performance for stability in Markov decision processes
• On the controller synthesis for finite-state Markov decision processes
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Variability Sensitive Markov Decision Processes
• Markov decision problems where means bound variances

Cites work

• scientific article; zbMATH DE number 46153 (Why is no real title available?)
• scientific article; zbMATH DE number 1348599 (Why is no real title available?)
• An \(O(n^2)\) time algorithm for alternating Büchi games
• Approximation algorithms for indefinite quadratic programming
• Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition
• Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification
• Finite state Markovian decision processes
• Markov Chains
• Markov Decision Processes with Multiple Objectives
• Markov decision processes and regular events
• Markov decision processes with multiple long-run average objectives
• Mean-Variance Tradeoffs in an Undiscounted MDP
• Mean-Variance Tradeoffs in an Undiscounted MDP: The Unichain Case
• Multi-Objective Model Checking of Markov Decision Processes
• Pareto curves for probabilistic model checking
• Quadratic programming is in NP
• Quadratic programming with one negative eigenvalue is NP-hard
• Quantitative multi-objective verification for probabilistic systems
• Some NP-complete problems in quadratic and nonlinear programming
• Strong laws of large numbers for weakly correlated random variables
• Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives
• The variance of discounted Markov decision processes
• Trading performance for stability in Markov decision processes
• Variance-Penalized Markov Decision Processes

Cited in

(11)

• Life is random, time is not: Markov decision processes with window objectives
• Multi-objective optimization of long-run average and total rewards
• CONIC TRADING IN A MARKOVIAN STEADY STATE
• Entropic risk for turn-based stochastic games
• Timed games with bounded window parity objectives
• Multi-cost bounded tradeoff analysis in MDP
• A Stochastic Approximation Approach for Trend-Following Trading
• scientific article; zbMATH DE number 7649916 (Why is no real title available?)
• Trading strategies generated by Lyapunov functions
• Trading performance for stability in Markov decision processes
• Stochastic games with lexicographic objectives

This page was built for publication: Trading performance for stability in Markov decision processes

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