Scholarlink

<p>We study countably infinite Markov decision processes with Büchi objectives, which ask to visit a given subset of states infinitely often. A question left open by T.P. Hill (<CitationRef CitationID="CR10">1979</CitationRef>) is whether there always exist <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation>-optimal Markov strategies, i.e., strategies that base decisions only on the current state and on the clock (the number of steps taken so far). We provide a negative answer to this question by constructing a non-trivial counterexample.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

No good Markov strategies for Büchi objectives in countable MDPs

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月9日

查看全文
  • Stefan Kiefer,
  • Richard Mayr,
  • Mahsa Shirmohammadi,
  • Patrick Totzke

摘要

We study countably infinite Markov decision processes with Büchi objectives, which ask to visit a given subset of states infinitely often. A question left open by T.P. Hill (1979) is whether there always exist \(\varepsilon \) ε -optimal Markov strategies, i.e., strategies that base decisions only on the current state and on the clock (the number of steps taken so far). We provide a negative answer to this question by constructing a non-trivial counterexample.