[{"volume":3884,"page":"325 - 336","OA_type":"closed access","date_updated":"2026-08-21T09:46:06Z","_id":"4551","title":"Markov decision processes with multiple objectives","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with multiple discounted reward 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 achieved by a memoryless strategy; however, unlike in the single-objective case, the memoryless strategy may require randomization. Moreover, we show that the Pareto curve can be approximated in polynomial time in the size of the MDP. 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; but the question whether it is realizable by a deterministic memoryless strategy is NP-complete. These results provide efficient algorithms for design exploration in MDP models with multiple objectives.\r\nThis research was supported in part by the AFOSR MURI grant F49620-00-1-0327, and the NSF grants CCR-0225610, CCR-0234690, and CCR-0427202. "}],"month":"02","intvolume":"      3884","year":"2006","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publisher":"Springer","acknowledgement":"This research was supported in part by the AFOSR MURI grant F49620-00-1-0327, and the NSF grants CCR-0225610, CCR-0234690, and CCR-0427202.","oa_version":"None","publication_identifier":{"issn":["0302-9743"],"eisbn":["9783540322887"],"isbn":["9783540323013"]},"publist_id":"161","extern":"1","alternative_title":["LNCS"],"author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Majumdar, Ritankar","first_name":"Ritankar","last_name":"Majumdar"},{"full_name":"Henzinger, Thomas A","first_name":"Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger"}],"date_created":"2018-12-11T12:09:26Z","day":"14","date_published":"2006-02-14T00:00:00Z","status":"public","citation":{"apa":"Chatterjee, K., Majumdar, R., &#38; Henzinger, T. A. (2006). Markov decision processes with multiple objectives. In <i>Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science</i> (Vol. 3884, pp. 325–336). Marseille, France: Springer. <a href=\"https://doi.org/10.1007/11672142_26\">https://doi.org/10.1007/11672142_26</a>","ieee":"K. Chatterjee, R. Majumdar, and T. A. Henzinger, “Markov decision processes with multiple objectives,” in <i>Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science</i>, Marseille, France, 2006, vol. 3884, pp. 325–336.","chicago":"Chatterjee, Krishnendu, Ritankar Majumdar, and Thomas A Henzinger. “Markov Decision Processes with Multiple Objectives.” In <i>Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer Science</i>, 3884:325–36. Springer, 2006. <a href=\"https://doi.org/10.1007/11672142_26\">https://doi.org/10.1007/11672142_26</a>.","short":"K. Chatterjee, R. Majumdar, T.A. Henzinger, in:, Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer Science, Springer, 2006, pp. 325–336.","ama":"Chatterjee K, Majumdar R, Henzinger TA. Markov decision processes with multiple objectives. In: <i>Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer Science</i>. Vol 3884. Springer; 2006:325-336. doi:<a href=\"https://doi.org/10.1007/11672142_26\">10.1007/11672142_26</a>","mla":"Chatterjee, Krishnendu, et al. “Markov Decision Processes with Multiple Objectives.” <i>Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer Science</i>, vol. 3884, Springer, 2006, pp. 325–36, doi:<a href=\"https://doi.org/10.1007/11672142_26\">10.1007/11672142_26</a>.","ista":"Chatterjee K, Majumdar R, Henzinger TA. 2006. Markov decision processes with multiple objectives. Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science. STACS: Theoretical Aspects of Computer Science, LNCS, vol. 3884, 325–336."},"language":[{"iso":"eng"}],"article_processing_charge":"No","doi":"10.1007/11672142_26","type":"conference","publication":"Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science","conference":{"location":"Marseille, France","end_date":"2006-02-25","name":"STACS: Theoretical Aspects of Computer Science","start_date":"2006-02-23"},"publication_status":"published"},{"publication":"Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science","conference":{"name":"STACS: Theoretical Aspects of Computer Science","end_date":"2006-02-25","start_date":"2006-02-23","location":"Marseille, France"},"publication_status":"published","oa_version":"None","citation":{"ieee":"K. Chatterjee and T. A. Henzinger, “Strategy improvement and randomized subexponential algorithms for stochastic parity games,” in <i>Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science</i>, Marseille, France, 2006, vol. 3884, pp. 512–523.","apa":"Chatterjee, K., &#38; Henzinger, T. A. (2006). Strategy improvement and randomized subexponential algorithms for stochastic parity games. In <i>Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science</i> (Vol. 3884, pp. 512–523). Marseille, France: Springer. <a href=\"https://doi.org/10.1007/11672142_42\">https://doi.org/10.1007/11672142_42</a>","short":"K. Chatterjee, T.A. Henzinger, in:, Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer Science, Springer, 2006, pp. 512–523.","chicago":"Chatterjee, Krishnendu, and Thomas A Henzinger. “Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games.” In <i>Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer Science</i>, 3884:512–23. Springer, 2006. <a href=\"https://doi.org/10.1007/11672142_42\">https://doi.org/10.1007/11672142_42</a>.","ama":"Chatterjee K, Henzinger TA. Strategy improvement and randomized subexponential algorithms for stochastic parity games. In: <i>Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer Science</i>. Vol 3884. Springer; 2006:512-523. doi:<a href=\"https://doi.org/10.1007/11672142_42\">10.1007/11672142_42</a>","ista":"Chatterjee K, Henzinger TA. 2006. Strategy improvement and randomized subexponential algorithms for stochastic parity games. Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science. STACS: Theoretical Aspects of Computer Science, LNCS, vol. 3884, 512–523.","mla":"Chatterjee, Krishnendu, and Thomas A. Henzinger. “Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games.” <i>Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer Science</i>, vol. 3884, Springer, 2006, pp. 512–23, doi:<a href=\"https://doi.org/10.1007/11672142_42\">10.1007/11672142_42</a>."},"language":[{"iso":"eng"}],"article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","status":"public","year":"2006","doi":"10.1007/11672142_42","type":"conference","publisher":"Springer","day":"14","date_published":"2006-02-14T00:00:00Z","month":"02","intvolume":"      3884","abstract":[{"lang":"eng","text":"A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with ω-regular winning conditions specified as parity objectives. These games lie in NP ∩ coNP. We present a strategy improvement algorithm for stochastic parity games; this is the first non-brute-force algorithm for solving these games. From the strategy improvement algorithm we obtain a randomized subexponential-time algorithm to solve such games."}],"alternative_title":["LNCS"],"OA_type":"closed access","page":"512 - 523","volume":3884,"publication_identifier":{"eisbn":["9783540322887"],"isbn":["9783540323013"],"eissn":["1611-3349"],"issn":["0302-9743"]},"extern":"1","publist_id":"184","date_created":"2018-12-11T12:09:22Z","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","full_name":"Henzinger, Thomas A"}],"date_updated":"2026-08-21T10:42:04Z","_id":"4538","title":"Strategy improvement and randomized subexponential algorithms for stochastic parity games"}]