You are in : Home » Results & submissions » Select UOA » 11 - Computer Science and Informatics » View submission: University of Edinburgh » Outputs » Detail

Output details

11 - Computer Science and Informatics

University of Edinburgh

Return to search Previous output Next output

Output 0 of 0 in the submission

Output title

One-counter Markov decision processes

Type

E - Conference contribution

DOI

Name of conference/published proceedings

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10)

Volume number

Issue number

First page of article

863

ISSN of proceedings

Year of publication

2010

URL

http://portal.acm.org/citation.cfm?id=1873601.1873671

Number of additional authors

Additional information

<12> Originality: The first polynomial-time algorithm for qualitative (i.e., with probability equal to one) termination analysis of one-counter Markov Decision Processes (OC-MDPs), a class of infinite-state MDPs that extend (discrete-time-)Quasi-Birth-Death processes (QBDs) with a controller, where the objective is to maximize (or minimize) the probability of termination. Other computability and complexity results for OC-MDPs are presented.

Significance: Heavily-studied in classical queuing-theory, QBDs correspond to Markov chain extensions of one-counter-automata. Their MDP-extension allows modelling adversarial queuing, and some risk-averse investment scenarios.

Rigour: Published in a highly-competitive international algorithms conference. Full paper (on ArXiv) is 36 pages with detailed mathematical proofs.

Interdisciplinary

Cross-referral requested

Research group

F - Laboratory for Foundations of Computer Science

Citation count

Proposed double-weighted

Double-weighted statement

Reserve for a double-weighted output

Non-English

English abstract