---
OA_type: closed access
_id: '4551'
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. "
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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Ritankar
  full_name: Majumdar, Ritankar
  last_name: Majumdar
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
citation:
  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>'
  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>'
  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>.
  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.
  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.'
  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>.
  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.
conference:
  end_date: 2006-02-25
  location: Marseille, France
  name: 'STACS: Theoretical Aspects of Computer Science'
  start_date: 2006-02-23
date_created: 2018-12-11T12:09:26Z
date_published: 2006-02-14T00:00:00Z
date_updated: 2026-08-21T09:46:06Z
day: '14'
doi: 10.1007/11672142_26
extern: '1'
intvolume: '      3884'
language:
- iso: eng
month: '02'
oa_version: None
page: 325 - 336
publication: Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer
  Science
publication_identifier:
  eisbn:
  - '9783540322887'
  isbn:
  - '9783540323013'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer
publist_id: '161'
status: public
title: Markov decision processes with multiple objectives
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 3884
year: '2006'
...
---
OA_type: closed access
_id: '4538'
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
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
citation:
  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>'
  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>'
  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>.
  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.
  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>.
  short: K. Chatterjee, T.A. Henzinger, in:, Proceedings of the 23rd Annual Conference
    on Theoretical Aspects of Computer Science, Springer, 2006, pp. 512–523.
conference:
  end_date: 2006-02-25
  location: Marseille, France
  name: 'STACS: Theoretical Aspects of Computer Science'
  start_date: 2006-02-23
date_created: 2018-12-11T12:09:22Z
date_published: 2006-02-14T00:00:00Z
date_updated: 2026-08-21T10:42:04Z
day: '14'
doi: 10.1007/11672142_42
extern: '1'
intvolume: '      3884'
language:
- iso: eng
month: '02'
oa_version: None
page: 512 - 523
publication: Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer
  Science
publication_identifier:
  eisbn:
  - '9783540322887'
  eissn:
  - 1611-3349
  isbn:
  - '9783540323013'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer
publist_id: '184'
status: public
title: Strategy improvement and randomized subexponential algorithms for stochastic
  parity games
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 3884
year: '2006'
...