*banner
 

Markov Decision Processes with Multiple Long-run Average Objectives
Krishnendu Chatterjee

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

Citation formats  
  • 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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess