About: One-Counter Markov Decision Processes

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

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)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
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	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), Z(MSM0021622419)
http://linked.open...vai/riv/dodaniDat	2011
http://linked.open...aciTvurceVysledku	Brázdil, Tomáš Brožek, Václav Kučera, Antonín
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	276974
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/10:00043501
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Markov decision proces; probability; one counter MDP; reachability; termination (en)
http://linked.open.../riv/klicoveSlovo	termination probability reachability Markov decision proces one counter MDP
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	IN
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	5 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science
http://linked.open...UplatneniVysledku	2010
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	WRD - Světová
http://linked.open...ain/vavai/riv/wos	000280699900070
http://linked.open.../riv/zahajeniAkce	2010-01-01 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
number of pages	12 (xsd:int)
http://purl.org/ne...btex#hasPublisher	SIAM
https://schema.org/isbn	978-0-89871-698-6
http://localhost/t...ganizacniJednotka	14330

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

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, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software