Output details
11 - Computer Science and Informatics
University of Edinburgh
One-counter Markov decision processes
<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.