Document Open Access Logo

Strategy Complexity of Parity Objectives in Countable MDPs

Authors Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke

PDF

File

Thumbnail PDF
PDF
LIPIcs.CONCUR.2020.39.pdf
  • Filesize: 0.68 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Mathematics of computing → Probability and statistics
Keywords
  • Markov decision processes
  • Parity objectives
  • Levy’s zero-one law

Metrics

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

Abstract

We study countably infinite MDPs with parity objectives. Unlike in finite MDPs, optimal strategies need not exist, and may require infinite memory if they do. We provide a complete picture of the exact strategy complexity of ε-optimal strategies (and optimal strategies, where they exist) for all subclasses of parity objectives in the Mostowski hierarchy. Either MD-strategies, Markov strategies, or 1-bit Markov strategies are necessary and sufficient, depending on the number of colors, the branching degree of the MDP, and whether one considers ε-optimal or optimal strategies. In particular, 1-bit Markov strategies are necessary and sufficient for ε-optimal (resp. optimal) strategies for general parity objectives.

Cite As Get BibTex

Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Patrick Totzke. Strategy Complexity of Parity Objectives in Countable MDPs. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CONCUR.2020.39

Author Details

Stefan Kiefer
  • Department of Computer Science, University of Oxford, UK
Richard Mayr
  • School of Informatics, University of Edinburgh, UK
Mahsa Shirmohammadi
  • CNRS & IRIF, Université de Paris, FR
Patrick Totzke
  • Department of Computer Science, University of Liverpool, UK

Funding

  • Kiefer, Stefan: Supported by a Royal Society University Fellowship.

References

  1. P. Abbeel and A. Y. Ng. Learning first-order Markov models for control. In Advances in Neural Information Processing Systems 17. MIT Press, 2004. URL: http://papers.nips.cc/paper/2569-learning-first-order-markov-models-for-control.
  2. C. Baier and J.-P. Katoen. Principles of Model Checking. MIT Press, 2008. Google Scholar
  3. P. Billingsley. Probability and Measure. Wiley, 1995. Third Edition. Google Scholar
  4. V. D. Blondel and J. N. Tsitsiklis. A survey of computational complexity results in systems and control. Automatica, 2000. Google Scholar
  5. N. Bäuerle and U. Rieder. Markov Decision Processes with Applications to Finance. Springer-Verlag Berlin Heidelberg, 2011. Google Scholar
  6. K. Chatterjee, M. Jurdziński, and T. Henzinger. Quantitative stochastic parity games. In Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982808.
  7. E. M. Clarke, T. A. Henzinger, H. Veith, and R. Bloem, editors. Handbook of Model Checking. Springer, 2018. URL: http://dx.doi.org/10.1007/978-3-319-10575-8.
  8. E.M. Clarke, O. Grumberg, and D. Peled. Model Checking. MIT Press, December 1999. Google Scholar
  9. E. Grädel, W. Thomas, and T. Wilke, editors. Automata, Logics, and Infinite Games, LNCS, 2002. Google Scholar
  10. T. P. Hill. On the existence of good Markov strategies. Transactions of the American Mathematical Society, 1979. URL: http://dx.doi.org/10.1090/S0002-9947-1979-0517690-9.
  11. T. P. Hill. Goal problems in gambling theory. Revista de Matemática: Teoría y Aplicaciones, 1999. Google Scholar
  12. S. Kiefer, R. Mayr, M. Shirmohammadi, and P. Totzke. Büchi objectives in countable MDPs. In International Colloquium on Automata, Languages and Programming. LIPIcs, 2019. A technical report is available at https://arxiv.org/abs/1904.11573. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.119.
  13. S. Kiefer, R. Mayr, M. Shirmohammadi, and P. Totzke. Strategy Complexity of Parity Objectives in Countable MDPs. CoRR, 2020. URL: http://arxiv.org/abs/2007.05065.
  14. S. Kiefer, R. Mayr, M. Shirmohammadi, and D. Wojtczak. Parity objectives in countable MDPs. In Annual IEEE Symposium on Logic in Computer Science, 2017. Google Scholar
  15. A. Mostowski. Regular expressions for infinite trees and a standard form of automata. In Computation Theory, LNCS, 1984. Google Scholar
  16. D. Ornstein. On the existence of stationary optimal strategies. Proceedings of the American Mathematical Society, 1969. Google Scholar
  17. M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., 1st edition, 1994. Google Scholar
  18. M. Schäl. Markov decision processes in finance and dynamic options. In Handbook of Markov Decision Processes. Springer, 2002. Google Scholar
  19. O. Sigaud and O. Buffet. Markov Decision Processes in Artificial Intelligence. John Wiley & Sons, 2013. Google Scholar
  20. R.S. Sutton and A.G Barto. Reinforcement Learning: An Introduction. Adaptive Computation and Machine Learning. MIT Press, 2018. Google Scholar
  21. M.Y. Vardi. Automatic verification of probabilistic concurrent finite-state programs. In Proc. of FOCS'85, 1985. Google Scholar
  22. W. Zielonka. Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoretical Computer Science, 1998. Google Scholar
  23. W. Zielonka. Perfect-information stochastic parity games. In Foundations of Software Science and Computation Structures, LNCS. Springer, 2004. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact