Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

One-Counter Markov Decision Processes

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F10%3A00043501" target="_blank" >RIV/00216224:14330/10:00043501 - isvavai.cz</a>

  • Výsledek na webu

  • DOI - Digital Object Identifier

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    One-Counter Markov Decision Processes

  • Popis výsledku v původním jazyce

    We study One-Counter Markov Decision Processes (OC-MDPs), which extend finite-state MDPs with an unbounded counter. The counter can be incremented, decremented, or not changed during each state transition. Basic objectives for OC-MDPs include ``termination'' (Does the OC-MDP reach counter 0?) and ``limit'' questions (Is the limsup value infinity?). We may ask what is the optimal probability of such objectives, or ask for the existence and synthesis of optimal strategies. We show that several quantitative and almost-sure limit problems can be answered in polynomial time, and that almost-sure termination problems (without selection of desired terminal states) can also be answered in polynomial time. On the other hand, we show that the almost-sure termination problem with selected terminal states is PSPACE-hard and we provide an exponential time algorithm for this problem. We also characterize classes of strategies that suffice for optimality in several of these settings.

  • Název v anglickém jazyce

    One-Counter Markov Decision Processes

  • Popis výsledku anglicky

    We study One-Counter Markov Decision Processes (OC-MDPs), which extend finite-state MDPs with an unbounded counter. The counter can be incremented, decremented, or not changed during each state transition. Basic objectives for OC-MDPs include ``termination'' (Does the OC-MDP reach counter 0?) and ``limit'' questions (Is the limsup value infinity?). We may ask what is the optimal probability of such objectives, or ask for the existence and synthesis of optimal strategies. We show that several quantitative and almost-sure limit problems can be answered in polynomial time, and that almost-sure termination problems (without selection of desired terminal states) can also be answered in polynomial time. On the other hand, we show that the almost-sure termination problem with selected terminal states is PSPACE-hard and we provide an exponential time algorithm for this problem. We also characterize classes of strategies that suffice for optimality in several of these settings.

Klasifikace

  • Druh

    D - Stať ve sborníku

  • CEP obor

    IN - Informatika

  • OECD FORD obor

Návaznosti výsledku

  • Projekt

    <a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

  • Návaznosti

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Ostatní

  • Rok uplatnění

    2010

  • Kód důvěrnosti údajů

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Údaje specifické pro druh výsledku

  • Název statě ve sborníku

    Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms

  • ISBN

    978-0-89871-698-6

  • ISSN

  • e-ISSN

  • Počet stran výsledku

    12

  • Strana od-do

  • Název nakladatele

    SIAM

  • Místo vydání

    Neuveden

  • Místo konání akce

    Austin (Texas, USA)

  • Datum konání akce

    1. 1. 2010

  • Typ akce podle státní příslušnosti

    WRD - Celosvětová akce

  • Kód UT WoS článku

    000280699900070