About: One-Counter Markov Decision Processes     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

AttributesValues
rdf:type
Description
  • 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.
  • 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. (en)
Title
  • One-Counter Markov Decision Processes
  • One-Counter Markov Decision Processes (en)
skos:prefLabel
  • One-Counter Markov Decision Processes
  • One-Counter Markov Decision Processes (en)
skos:notation
  • RIV/00216224:14330/10:00043501!RIV11-MSM-14330___
http://linked.open...avai/riv/aktivita
http://linked.open...avai/riv/aktivity
  • P(1M0545), Z(MSM0021622419)
http://linked.open...vai/riv/dodaniDat
http://linked.open...aciTvurceVysledku
http://linked.open.../riv/druhVysledku
http://linked.open...iv/duvernostUdaju
http://linked.open...titaPredkladatele
http://linked.open...dnocenehoVysledku
  • 276974
http://linked.open...ai/riv/idVysledku
  • RIV/00216224:14330/10:00043501
http://linked.open...riv/jazykVysledku
http://linked.open.../riv/klicovaSlova
  • Markov decision proces; probability; one counter MDP; reachability; termination (en)
http://linked.open.../riv/klicoveSlovo
http://linked.open...ontrolniKodProRIV
  • [E220ADC7D750]
http://linked.open...v/mistoKonaniAkce
  • Austin (Texas, USA)
http://linked.open...i/riv/mistoVydani
  • Neuveden
http://linked.open...i/riv/nazevZdroje
  • Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms
http://linked.open...in/vavai/riv/obor
http://linked.open...ichTvurcuVysledku
http://linked.open...cetTvurcuVysledku
http://linked.open...vavai/riv/projekt
http://linked.open...UplatneniVysledku
http://linked.open...iv/tvurceVysledku
  • Brožek, Václav
  • Brázdil, Tomáš
  • Etessami, Kousha
  • Kučera, Antonín
  • Wojtczak, Dominik
http://linked.open...vavai/riv/typAkce
http://linked.open...ain/vavai/riv/wos
  • 000280699900070
http://linked.open.../riv/zahajeniAkce
http://linked.open...n/vavai/riv/zamer
number of pages
http://purl.org/ne...btex#hasPublisher
  • SIAM
https://schema.org/isbn
  • 978-0-89871-698-6
http://localhost/t...ganizacniJednotka
  • 14330
is http://linked.open...avai/riv/vysledek of
Faceted Search & Find service v1.16.118 as of Jun 21 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 112 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software