Citation
Krishnendu Chatterjee. "Markov Decision Processes with Multiple Long-run Average Objectives". FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 473-484, December, 2007.

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 approximated by a memoryless strategy, for all. 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.

Electronic downloads

• fsttcs07-59.pdf · / · 180 kbytes
• http://dx.doi.org/10.1007/978-3-540-77050-3_39

• HTML

  Krishnendu Chatterjee. <a
  href="http://chess.eecs.berkeley.edu/pubs/466.html"
  >Markov Decision Processes with Multiple Long-run Average
  Objectives</a>, 	FSTTCS 2007: Foundations of Software
  Technology and Theoretical Computer Science, 473-484,
  December, 2007.

• Plain text

  Krishnendu Chatterjee. "Markov Decision Processes with
  Multiple Long-run Average Objectives". 	FSTTCS 2007:
  Foundations of Software Technology and Theoretical Computer
  Science, 473-484, December, 2007.

• BibTeX

  @inproceedings{Chatterjee07_MarkovDecisionProcessesWithMultipleLongrunAverageObjectives,
      author = {Krishnendu Chatterjee},
      title = {Markov Decision Processes with Multiple Long-run
                Average Objectives},
      booktitle = {	FSTTCS 2007: Foundations of Software Technology
                and Theoretical Computer Science},
      pages = {473-484},
      month = {December},
      year = {2007},
      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 approximated by
                a memoryless strategy, for all. 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.},
      URL = {http://chess.eecs.berkeley.edu/pubs/466.html}
  }
  

Posted by Krishnendu Chatterjee, PhD on 24 Jun 2008.
Groups: chess
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.