Markov decision processes with multiple long-run average objectives

K. Chatterjee, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2007, pp. 473–484.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Series Title
LNCS
Abstract
We consider Markov decision processes (MDPs) with multiple long-run average objectives. Such MDPs occur in design problems where one wishes to simultaneously optimize several criteria, for example, latency and power. The possible trade-offs between the different objectives are characterized by the Pareto curve. We show that every Pareto optimal point can be epsilon-approximated by a memoryless strategy, for all epsilon > 0. In contrast to the single-objective case, the memoryless strategy may require randomization. We show that the Pareto curve can be approximated (a) in polynomial time in the size of the MDP for irreducible MDPs; and (b) in polynomial space in the size of the MDP for all MDPs. Additionally, we study the problem if a given value vector is realizable by any strategy, and show that it can be decided in polynomial time for irreducible MDPs and in NP for all MDPs. These results provide algorithms for design exploration in MDP models with multiple long-run average objectives.
Publishing Year
Date Published
2007-11-27
Acknowledgement
This research was supported by the NSF grants CCR-0225610 and CCR-0234690
Volume
4855
Page
473 - 484
Conference
FSTTCS: Foundations of Software Technology and Theoretical Computer Science
IST-REx-ID

Cite this

Chatterjee K. Markov decision processes with multiple long-run average objectives. In: Vol 4855. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2007:473-484. doi:10.1007/978-3-540-77050-3_39
Chatterjee, K. (2007). Markov decision processes with multiple long-run average objectives (Vol. 4855, pp. 473–484). Presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/978-3-540-77050-3_39
Chatterjee, Krishnendu. “Markov Decision Processes with Multiple Long-Run Average Objectives,” 4855:473–84. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2007. https://doi.org/10.1007/978-3-540-77050-3_39.
K. Chatterjee, “Markov decision processes with multiple long-run average objectives,” presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, 2007, vol. 4855, pp. 473–484.
Chatterjee K. 2007. Markov decision processes with multiple long-run average objectives. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LNCS , vol. 4855. 473–484.
Chatterjee, Krishnendu. Markov Decision Processes with Multiple Long-Run Average Objectives. Vol. 4855, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2007, pp. 473–84, doi:10.1007/978-3-540-77050-3_39.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar