Document Open Access Logo

Expected Window Mean-Payoff

Authors Benjamin Bordais, Shibashis Guha, Jean-François Raskin

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.32.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Benjamin Bordais
  • ENS Rennes, France
Shibashis Guha
  • Université libre de Bruxelles, Belgium
Jean-François Raskin
  • Université libre de Bruxelles, Belgium

Funding

Work partially supported by the ARC project Non-Zero Sum Game Graphs: Applications to Reactive Synthesis and Beyond (Fédération Wallonie-Bruxelles), and the EOS project Verifying Learning Artificial Intelligence Systems (F.R.S.-FNRS & FWO).

Cite AsGet BibTex

Benjamin Bordais, Shibashis Guha, and Jean-François Raskin. Expected Window Mean-Payoff. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.32

Abstract

We study the expected value of the window mean-payoff measure in Markov decision processes (MDPs) and Markov chains (MCs). The window mean-payoff measure strengthens the classical mean-payoff measure by measuring the mean-payoff over a window of bounded length that slides along an infinite path. This measure ensures better stability properties than the classical mean-payoff. Window mean-payoff has been introduced previously for two-player zero-sum games. As in the case of games, we study several variants of this definition: the measure can be defined to be prefix-independent or not, and for a fixed window length or for a window length that is left parametric. For fixed window length, we provide polynomial time algorithms for the prefix-independent version for both MDPs and MCs. When the length is left parametric, the problem of computing the expected value on MDPs is as hard as computing the mean-payoff value in two-player zero-sum games, a problem for which it is not known if it can be solved in polynomial time. For the prefix-dependent version, surprisingly, the expected window mean-payoff value cannot be computed in polynomial time unless P=PSPACE. For the parametric case and the prefix-dependent case, we manage to obtain algorithms with better complexities for MCs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Stochastic processes
  • Mathematics of computing → Probability and statistics
Keywords
  • mean-payoff
  • Markov decision processes
  • synthesis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT Press, 2008. Google Scholar
  2. Benjamin Bordais, Shibashis Guha, and Jean-François Raskin. Expected Window Mean-Payoff. CoRR, abs/1812.09298, 2018. URL: http://arxiv.org/abs/1812.09298.
  3. Tomás Brázdil, Václav Brozek, Krishnendu Chatterjee, Vojtech Forejt, and Antonín Kucera. Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. Logical Methods in Computer Science, 10(1), 2014. Google Scholar
  4. Tomás Brázdil, Krishnendu Chatterjee, Vojtech Forejt, and Antonín Kucera. Trading performance for stability in Markov decision processes. J. Comput. Syst. Sci., 84:144-170, 2017. Google Scholar
  5. Tomás Brázdil, Vojtech Forejt, Antonín Kucera, and Petr Novotný. Stability in Graphs and Games. In 27th International Conference on Concurrency Theory, CONCUR 2016, August 23-26, 2016, Québec City, Canada, volume 59 of LIPIcs, pages 10:1-10:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  6. Thomas Brihaye, Florent Delgrange, Youssouf Oualhadj, and Mickael Randour. Life is Random, Time is Not: Markov Decision Processes with Window Objectives. CoRR, abs/1901.03571, 2019. URL: http://arxiv.org/abs/1901.03571.
  7. Véronique Bruyère, Quentin Hautem, and Jean-François Raskin. On the Complexity of Heterogeneous Multidimensional Games. In 27th International Conference on Concurrency Theory, CONCUR 2016, August 23-26, 2016, Québec City, Canada, volume 59 of LIPIcs, pages 11:1-11:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  8. Krishnendu Chatterjee, Laurent Doyen, Mickael Randour, and Jean-François Raskin. Looking at Mean-Payoff and Total-Payoff through Windows. In Automated Technology for Verification and Analysis - 11th International Symposium, ATVA 2013, Hanoi, Vietnam, October 15-18, 2013. Proceedings, volume 8172 of Lecture Notes in Computer Science, pages 118-132. Springer, 2013. Google Scholar
  9. Krishnendu Chatterjee, Laurent Doyen, Mickael Randour, and Jean-François Raskin. Looking at mean-payoff and total-payoff through windows. Inf. Comput., 242:25-52, 2015. Google Scholar
  10. Krishnendu Chatterjee and Monika Henzinger. Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition. J. ACM, 61(3):15:1-15:40, June 2014. Google Scholar
  11. Luca De Alfaro. Formal Verification of Probabilistic Systems. PhD thesis, Stanford University, Stanford, CA, USA, 1998. Google Scholar
  12. Christoph Haase and Stefan Kiefer. The Odds of Staying on Budget. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, pages 234-246, 2015. Google Scholar
  13. Paul Hunter, Guillermo A. Pérez, and Jean-François Raskin. Looking at mean payoff through foggy windows. Acta Inf., 55(8):627-647, 2018. Google Scholar
  14. Marcin Jurdzinski. Deciding the Winner in Parity Games is in UP ∩ co-UP. Inf. Process. Lett., 68(3):119-124, 1998. Google Scholar
  15. Richard M. Karp. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23:309-311, 1978. Google Scholar
  16. Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1994. Google Scholar
  17. Moshe Y. Vardi. Automatic Verification of Probabilistic Concurrent Finite-State Programs. In 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985, pages 327-338. IEEE Computer Society, 1985. Google Scholar
  18. Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. Theoretical Computer Science, 158(1-2):343-359, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact