Earlier Version

Trading performance for stability in Markov decision processes

T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, in:, 28th Annual ACM/IEEE Symposium, IEEE, 2013, pp. 331–340.


Conference Paper | Published | English
Author
; ; ;
Department
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. e 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.
Publishing Year
Date Published
2013-08-01
Proceedings Title
28th Annual ACM/IEEE Symposium
Page
331 - 340
Conference
LICS: Logic in Computer Science
Conference Location
New Orleans, LA, United States
Conference Date
2013-06-25 – 2013-06-28
IST-REx-ID

Cite this

Brázdil T, Chatterjee K, Forejt V, Kučera A. Trading performance for stability in Markov decision processes. In: 28th Annual ACM/IEEE Symposium. IEEE; 2013:331-340. doi:10.1109/LICS.2013.39
Brázdil, T., Chatterjee, K., Forejt, V., & Kučera, A. (2013). Trading performance for stability in Markov decision processes. In 28th Annual ACM/IEEE Symposium (pp. 331–340). New Orleans, LA, United States: IEEE. https://doi.org/10.1109/LICS.2013.39
Brázdil, Tomáš, Krishnendu Chatterjee, Vojtěch Forejt, and Antonín Kučera. “Trading Performance for Stability in Markov Decision Processes.” In 28th Annual ACM/IEEE Symposium, 331–40. IEEE, 2013. https://doi.org/10.1109/LICS.2013.39.
T. Brázdil, K. Chatterjee, V. Forejt, and A. Kučera, “Trading performance for stability in Markov decision processes,” in 28th Annual ACM/IEEE Symposium, New Orleans, LA, United States, 2013, pp. 331–340.
Brázdil T, Chatterjee K, Forejt V, Kučera A. 2013. Trading performance for stability in Markov decision processes. 28th Annual ACM/IEEE Symposium. LICS: Logic in Computer Science 331–340.
Brázdil, Tomáš, et al. “Trading Performance for Stability in Markov Decision Processes.” 28th Annual ACM/IEEE Symposium, IEEE, 2013, pp. 331–40, doi:10.1109/LICS.2013.39.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1305.4103

Search this title in

Google Scholar