首页    期刊浏览 2025年02月17日 星期一
登录注册

文章基本信息

  • 标题:Büchi Objectives in Countable MDPs
  • 本地全文:下载
  • 作者:Stefan Kiefer ; Richard Mayr ; Mahsa Shirmohammadi
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2019
  • 卷号:132
  • 页码:1-14
  • DOI:10.4230/LIPIcs.ICALP.2019.119
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We study countably infinite Markov decision processes with Büchi objectives, which ask to visit a given subset F of states infinitely often. A question left open by T.P. Hill in 1979 [Theodore Preston Hill, 1979] is whether there always exist epsilon-optimal Markov strategies, i.e., strategies that base decisions only on the current state and the number of steps taken so far. We provide a negative answer to this question by constructing a non-trivial counterexample. On the other hand, we show that Markov strategies with only 1 bit of extra memory are sufficient.
  • 关键词:Markov decision processes
国家哲学社会科学文献中心版权所有